What are some of the best sources (books and papers) to motivate and learn communication complexity on its own and in connection with its relation to computational complexity theory?
$\begingroup$
$\endgroup$
0
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
3
Books:
Eyal Kushilevitz and Noam Nisan, "Communication Complexity", 2006.
Stasys Jukna, "Boolean Function Complexity: Advances and Frontiers", 2012. (Part II of the book is dedicated to Communication Complexity.)
Articles:
- Alexander Razborov, "Communication Complexity".
Lecture Notes:
Toni Pitassi, "Communication Complexity, Information Complexity and Applications", 2012
Ran Raz, "Circuit Complexity and Communication Complexity".
Also check Sasha's remarks about communication complexity.
-
3$\begingroup$ The recent book by Stasys Jukna is fantastic amazon.com/Boolean-Function-Complexity-Algorithms-Combinatorics/… $\endgroup$ Mar 7, 2014 at 1:17
-
2$\begingroup$ I've also found the old (1990) survey by Lovász useful for its conceptual stance; it is available from his web page at cs.elte.hu/~lovasz/commcomp.pdf $\endgroup$ Mar 7, 2014 at 11:12
-
5$\begingroup$ A more recent reference by Lee and Shraibman, also covers the methods to prove lower bound on quantum communication complexity research.rutgers.edu/~troyjlee/survey_plain.pdf $\endgroup$– pyaoMar 7, 2014 at 22:42