Neuere probabilistische Methoden in der Kombinatorik und ihre Anwendung auf die Komplexitätstheorie

8

Ich habe das berühmte Buch von Alon und Spencer über die probabilistische Methode in der Kombinatorik gelesen.

Gibt es eine Umfrage oder Vorlesungsunterlagen zu den jüngsten Fortschritten und Beziehungen zu den folgenden komplexitätstheoretischen Themen dieser Methode über dieses Lehrbuch hinaus?

  1. Pseudozufallsgeneratoren, die konkrete Berechnungsmodelle täuschen, Expander-Graphen.

  2. Komplexitätsuntergrenzen für konkrete Berechnungsmodelle wie Schaltungen, Verzweigungsprogramme, Streaming, Eigenschaftstests, Lernen und Kommunikationskomplexität.

  3. Randomisierte komplexitätstheoretische Aspekte der algebraischen Codierungstheorie und Informationstheorie.

  4. VC-Dimension, Diskrepanz und andere geometrische Themen.

cc.complexity-theory reference-request co.combinatorics soft-question survey Shen
quelle

Antworten:

6

Ich empfehle Stasys Juknas Bücher Extremal Combinatorics und Boolean Function Complexity. Informationen zu Diskrepanzen und Ähnlichem finden Sie in Bernard Chazelles Buch The Discrepancy Method (online verfügbar auf seiner Homepage).

Yuval Filmus
quelle