Communication Complexity

Course Instructor: Anup Rao (anuprao@cs.washington.edu)

TA: Cyrus Rashtchian (cyrash@cs.washington.edu)

Communication complexity measures the number of bits that must be exchanged by two or more parties to compute some joint function of all of their inputs. In the past few decades, many lower bounds on computational models have been proved by reducing the computation to a communication problem, and then proving a lower bound on the communication required. In this course, we shall study the techniques used to prove lower bounds on communication in various contexts.

Course Resources:

Live draft of text: here.

Grading will be based on 3 take-home homework assignments:

Homework 1 (due October 23). Solutions.

Homework 2 (due December 4).

Collaboration is encouraged, but you must write up solutions by yourself.

Final Lecture (Friday, 12/11): We discuss lower bounds on dynamic data structures, and talk briefly about proving lower bounds on linear programs.

Schedule (updated as we go):

Week 1 [Sep 30, Oct 2]

  1. Basics, Chapter 1 in text.
  1. The 2 party Model.
  2. Protocol trees, # rounds.
  3. Partition complexity
  4. Yannakakis’s Protocol
  5. Protocol for cliques and independent sets
  6. Krapchenko’s method
  7. The fooling set method. Equality, disjointness

Week 2 [Oct 7, Oct 9]

  1. Rank, Chapter 2 in text.
  1. Lower bounds for Disjointness, inner product
  2. The log rank conjecture

Week 3 [Oct 14, 16]

  1. Communication is bounded by root of Rank
  2. Non-negative Rank
  3. Rectangle Covers, direct sums for deterministic communication

Week 4 [Oct 21, 23]

  1. Randomized Communication, Chapter 3 in text.
  1. Equality.
  2. Feige’s protocol for greater than.
  3. Protocol for k-disjointness
  4. The min-max theorem
  5. Newman’s result about public vs private coins.
  1. Number-On-Forehead model
  1. Grolmusz’s protocol and variants.

Week 5 [Oct 28, 30]

  1. Exactly-n protocol and lowerbound from Ramsey Theory
  1. Discrepancy
  1. Bounding discrepancy using Cauchy Schwartz
  2. Discrepancy tensorizes

Week 6,7 [Nov 4,  11, 13]

  1. Information complexity
  1. Basics of information with examples.
  2. Information vs discrepancy
  3. Lower bounds for computing Disjointness
  4. Small set disjointness
  5. Rounds vs communication

Week 8 [Nov 25] Current Week

  1. Protocol Compression
  2. Direct Sums and Products
  3. Separating Information and Communication
  4. Lower bound for greater than.

Week 9 [Dec 2, 4]

  1. Circuits, Branching programs
  1. Karchmer Wigderson, composition conjecture, monotone ckt lowerbounds.
  2. Chandra-Furst-Lipton and connections to Ramsey Theory (coloring lower bound for the corner’s problem).
  3. ACC, computing polynomials
  4. Size-depth tradeoff for boolean circuits (Valiant)
  5. Size-depth tradeoffs for branching programs
  1. Data Structures
  1. The cell-probe model
  2. Patrascu’s problem
  3. Lopsided disjointness and lowerbounds
  4. Richness
  5. Lower bounds for dynamic data structures for graph connectivity (Saks et. al)
  6. Larsen’s lower bound for static data structures

Week 10 [Dec 9, 11]

  1. Streaming lower bounds
  1. Gap hamming lower bound
  2. indexing
  1. Extension Complexity
  1. Non-negative rank.
  2. LP lower bounds via communication
  3. SDP lower bounds