Las mejores fuentes para la complejidad de la comunicación.

Respuestas:

12

Libros:

  • Eyal Kushilevitz y Noam Nisan, " Complejidad de la comunicación ", 2006.

  • Stasys Jukna, "Complejidad de la función booleana: avances y fronteras", 2012. (La parte II del libro está dedicada a la complejidad de la comunicación).

Artículos:

Notas de lectura:

También verifique los comentarios de Sasha sobre la complejidad de la comunicación .

Kaveh
fuente
3
El libro reciente de Stasys Jukna es fantástico amazon.com/Boolean-Function-Complexity-Algorithms-Combinatorics/…
Marcos Villagra
2
También he encontrado útil la antigua encuesta (Lovász) de 1990 (1990) por su postura conceptual; está disponible en su página web en cs.elte.hu/~lovasz/commcomp.pdf
András Salamon
55
Una referencia más reciente de Lee y Shraibman, también cubre los métodos para probar el límite inferior en la complejidad de la comunicación cuántica research.rutgers.edu/~troyjlee/survey_plain.pdf
pyao