Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 12 down vote accepted


  • 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.)


Lecture Notes:

Also check Sasha's remarks about communication complexity.

share|improve this answer
The recent book by Stasys Jukna is fantastic amazon.com/Boolean-Function-Complexity-Algorithms-Combinatorics/… –  Marcos Villagra Mar 7 '14 at 1:17
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 –  András Salamon Mar 7 '14 at 11:12
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 –  pyao Mar 7 '14 at 22:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.