Métodos probabilísticos recientes en combinatoria y sus aplicaciones a la teoría de la complejidad

8

Leí el famoso libro de Alon y Spencer sobre el método probabilístico en combinatoria.

¿Hay una encuesta o notas de conferencias sobre avances recientes y relaciones con los siguientes temas teóricos de complejidad de este método más allá de este libro de texto?

  1. generadores pseudoaleatorios que engañan a modelos concretos de computación, gráficos expansores.

  2. límites inferiores de complejidad para modelos de cómputo concretos como circuitos, programas de ramificación, transmisión, pruebas de propiedad, aprendizaje y complejidad de comunicación.

  3. aspectos teóricos de complejidad aleatoria de la teoría de codificación algebraica y la teoría de la información.

  4. Dimensión VC, discrepancia y otros temas geométricos.

shen
fuente

Respuestas:

6

Recomiendo mirar los libros de Stasys Jukna , Extremal Combinatorics y Boolean Function Complexity. Para discrepancias y cosas similares, puede consultar el libro de Bernard Chazelle , El método de discrepancia (disponible en línea en su página de inicio).

Yuval Filmus
fuente