Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
The recent book by Stasys Jukna is fantastic… – 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 – 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 – 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.