Beste Quellen für Kommunikationskomplexität

Antworten:

12

Bücher:

  • Eyal Kushilevitz und Noam Nisan, " Communication Complexity ", 2006.

  • Stasys Jukna, "Boolesche Funktionskomplexität: Fortschritte und Grenzen", 2012. (Teil II des Buches ist der Kommunikationskomplexität gewidmet.)

Artikel:

Vorlesungsnotizen:

Überprüfen Sie auch Sashas Bemerkungen zur Komplexität der Kommunikation .

Kaveh
quelle
3
Das jüngste Buch von Stasys Jukna ist fantastisch amazon.com/Boolean-Function-Complexity-Algorithms-Combinatorics/…
Marcos Villagra
2
Ich fand auch die alte (1990) Umfrage von Lovász nützlich für ihre konzeptionelle Haltung; es ist auf seiner Webseite unter cs.elte.hu/~lovasz/commcomp.pdf
András Salamon am
5
Eine neuere Referenz von Lee und Shraibman, erstreckt sich auch auf die Methoden niedriger auf Quantenkommunikation Komplexität gebunden zu beweisen research.rutgers.edu/~troyjlee/survey_plain.pdf
pyao