Communication and Information Complexity, Spring 2015

Course Material:

The first part of the course follows the book Communication Complexity by Eyal Kushilevitz and Noam Nisan. Lecture notes will be published for the rest of the course.

• Part I: combinatorial and algebraic lower bounds
  • Lecture 1: introduction to communication complexity; fooling set lower bound (section 1.3); Karchmer-Wigderson games and monotone circuit lower bound for matching (sections 10.1 - 10.3).
  • Lecture 2: rectangle size lower bound (section 1.3); rank lower bound and the log rank conjecture (section 1.4); nondeterministic communication complexity and relation to monochromatic covers (section 2.1); deterministic vs. nondeterministic communication complexity (section 2.3).
  • Lecture 3: communication complexity of k-disjointness (example 2.12); randomized vs. deterministic communication complexity (section 3.2); public-coin vs. private coin (section 3.3); Yao's minimax principle and distributional communication complexity (section 3.4).
  • Lecture 4: discrepancy bound (section 3.5); randomized communication complexity of inner product (example 3.29); corruption bound; randomized communication complexity of set disjointness under product distributions (see "The story of set disjointness", a SIGACT News Column by Chattopadhyay and Pitassi); streaming lower bounds using communication complexity (see "The space complexity of approximating the frequency moments" by Alon, Matias and Szegedy).
• Part II: information complexity
  • Lecture 5: basics of information theory; internal and external information cost; handling public and private randomness; external information complexity of Equality. (See "Interactive Information Complexity" by Braverman)
  • Lecture 6: internal information complexity of Equality; direct sum theorem; set disjointness lower bound (to be continued in the next lecture).
  • Lecture 7: set disjointness lower bound (continued); amortized compression for infinite block length (see Information Equals Amortized Communication" by Braverman,Rao
  • Lecture 8: compression, continued; compression to 2^I (see "Interactive Information Complexity" by Braverman; compression to \sqrt{I*C} (see "Direct Sums in Communication Complexity" by Barak, Braverman, Chen and Rao);
• Part III: applications and advanced topics
  • Lecture 9: streaming lower bounds using communication complexity; index lower bound using information complexity; reduction from index to gap hamming distance (see "The one-way communication complexity of Gap Hamming Distance" by Jayram, Kumar and Sivakumar). Introduction to the number-on-forehead model and its application in circuit lower bounds.

Homework:

To be submitted in writing/print at the end of class. You may discuss the homework with other students but each student must write their solutions alone. Indicate at the top of your submission who you discussed the homework with.

• Homework 1 (due 16.4)
• Homework 2 (due 30.4)
• Homework 3, part a (due 14.5)
• Homework 4 (due 28.5)

Final projects:

• Instructions
• Paper suggestions
• Project presentation dates

Syllabus:

1. Communication complexity: lower bound techniques for deterministic and randomized protocols; rectangle covers; nondeterministic communication complexity; Razborov's lower bound for Disjointness; applications.
2. Information complexity: definitions and relationship to communication; direct sum; the BJKS'04 lower bound for Disjointness; compression.
3. Advanced topics and applications: streaming lower bounds; Sherstov's lower bound for Gap Hamming Distance; data structure lower bounds in the cell-probe model; circuit and formula lower bounds and number-on-forehead multi-party communication; the Babai-Nisan-Szegedy lower bound for Generalized Inner Product; applications in distributed computing; other topics.