CS 285CC Communication Complexity

Description

Consider a function f whose arguments are distributed among several parties, making it impossible for any one party to compute f in isolation. Communication complexity theory studies how many bits of communication are needed to evaluate f. A trivial approach is for the parties to communicate their inputs to each other. While this costly solution is optimal in some cases, one can often accomplish the task with surprisingly little communication. To cite a famous example, one can check with accuracy 99% if two geographically separated databases are identical by communicating only eight bits, regardless of how large the databases actually are! Over the past three decades, communication complexity has evolved into a central area of theoretical computer science, with deep open questions, beautiful mathematics, and many applications.

This graduate course is a self-contained introduction to communication complexity, with coverage of the fundamentals, key classic theorems, and current research directions. It is a rigorous and mathematically demanding course, with an emphasis on proofs. Mathematical maturity is assumed.

Grading

• Scribe notes, 30%. Scribe notes are a complete and polished write-up of a given lecture, with bibliographic references and technical details carefully filled in. Every student should expect to scribe once or twice, depending on class size. At the beginning of every lecture, I will ask for two volunteers to be the scribes for the day. Each of you will be responsible for half of that day's lecture. Please do not volunteer if there is a chance that you will drop the course before you submit your scribe notes. Preparing the scribe notes will help you internalize the material at a new level, by thinking through the significance of the material and by completing every proof outline in class to a rigorous proof. Please typeset your scribe notes in LaTeX using the instructions and template below. You have one week to prepare the scribe notes. For example, the scribe notes for a Monday lecture are due at 2pm the following Monday (regardless of any intervening holidays). Please email me your .pdf file and the source files (.tex and .bib, as well as figure files if any). Please email me your files as a single ZIP archive; do not use compressed formats other than ZIP.

  Instructions

  Template

• Problem sets, 60% (= 2 × 30%). The first problem set will be handed about halfway through the course and the second, toward the end. The problem sets play the role of take-home midterm and final exams. Please see below for important policies on late submissions and academic honesty.
• Class participation, 10%. Class participation is essential for success in this class and will be graded on a credit/no credit basis.

Course Schedule

The course schedule below is tentative and may be adjusted in response to student interest and time constraints.

1. DETERMINISTIC COMMUNICATION
   • The model. Deterministic two-party communication. Protocols for equality, parity, median. Formal definition of a protocol. Tree representation of protocols. Communication complexity of random functions.
   • Fooling sets. Combinatorial rectangles. Global and local view of rectangles. Protocol-induced partition of the input space. The fooling set technique. Fooling sets for equality, greater-than, set disjointness, inner product. Fooling sets for random matrices.
   • The rank bound. The rank technique. Rank of equality, greater-than, inner product, set disjointness. Rank of random matrices. Rank vs. fooling sets. Log-rank conjecture on rank vs. communication complexity; known upper and lower bounds. Rank over the reals vs. finite fields.  Handout on fields
   • Covers. Cover number. Equivalence of deterministic communication complexity and cover number. Cover number of equality, set disjointness, greater-than, inner product. Cover number of random functions. Dual characterization of the cover number.
2. NONDETERMINISM
   • Nondeterminism. Nondeterminism as a proof system. Equivalence of proof systems and covers. Equivalence of deterministic and nondeterministic communication. Deterministic, nondeterministic, and co-nondeterministic complexity of k-set disjointness.
   • Polynomial hierarchy. Reductions. Communication classes P, NP, coNP. Completeness of set disjointness for coNP. Generalization to multiple quantifiers; polynomial hierarchy.
3. RANDOMIZED COMMUNICATION
   • Power of randomness. Randomized communication. Boosting accuracy by repetition. Randomized protocol for equality. Simulation of randomized protocols by deterministic ones with exponential slowdown; optimality for the equality problem. Sipser-Gács theorem.
   • Public randomness. Randomized communication with public randomness. Equivalence of private and public randomness up to a small additive term. Constant-cost protocol for equality, O(k) protocol for k-set disjointness, O(log² n) protocol for greater-than. Noisy comparison trees. O(log n) randomized protocol for greater-than; matching lower bound.
   • Discrepancy method. Distributional complexity. Combinatorial definition of discrepancy. Discrepancy as a characterization of cost-2 protocols. Alternate definitions of discrepancy. Cauchy-Schwarz analysis of discrepancy. Discrepancy of random functions and inner product. Randomized communication complexity of random functions and inner product.
   • Set disjointness. The nondeterminism barrier to the discrepancy method. Corruption bound. Linear lower bound on the randomized communication complexity of set disjointness. Complete picture of the relations among the communication classes P, NP, coNP, BPP, and the polynomial hierarchy.
   • Multiparty communication. Number-on-the-forehead model; motivation. Grolmusz's protocol for set disjointness and generalized inner product. Matching lower bound for generalized inner product.
4. GEOMETRIC METHODS
   • Geometry. Topology of Euclidean space; bounded, closed, convex, and compact sets. Separating hyperplane theorem for a compact and bounded sets. Separating hyperplane theorem for arbitrary convex sets. Zero-sum games. Minimax theorem for zero-sum games.  Handout on the separating hyperplane theorem.
   • Convex relaxations. Yao's minimax characterization of randomized communication. Geometric view of computation. Lower bounds as a search for a separating hyperplane. Convex relaxation of randomized communication as the convex hull of rectangles and their negations. Discrepancy method revisited. Generalized discrepancy method. Corruption bound revisited.
5. SPECTRAL METHODS
   • Matrix analysis. Singular value decomposition; existence and uniqueness. Minimax characterization of the singular values. Orthogonal diagonalization of symmetric matrices. Positive semidefinite and definite matrices; definition and alternate characterizations. Matrix norms. Frobenius norm, spectral norm, trace norm; characterization in terms of singular values. Spectral lower bound on discrepancy.
   • Gap Hamming distance. Talagrand's concentration inequality. Concentration of the distance of a random Boolean vector from a given linear subspace. Gap Hamming distance and gap orthogonality; sampling-based communication protocols. Matching lower bounds on communication.
   • Unbounded-error communication. Unbounded-error communication as the limit of private-coin randomized communication with ε→1/2. Private vs. public randomness; a cost-2 protocol for every function with public randomness. Sign-rank; equivalence to unbounded-error communication. Arbitrarily large gaps between rank and sign-rank. Isotropic position. Linear lower bound on the unbounded-error complexity of inner product.
6. QUANTUM COMMUNICATION
   • Norm theory. Analytic and geometric properties of norms in Euclidean space. Duality theorem for norms. Dual pairs of previously introduced vector and matrix norms. Communication-based norms μ, ν, γ₂. Grothendieck's inequality; proof due to Rietz. Equivalence of μ, ν, γ₂ up to small constant factors.
   • Quantum communication. Quantum circuits. Circuit view of communication. Definitions of quantum communication in terms of circuits and matrix analysis. Quantum protocol for set disjointness using Grover's search. Convex relaxation of quantum communication in terms of the γ₂ norm. Lower bounds on quantum communication via discrepancy and generalized discrepancy.
   • Pattern matrix method. Statement of the method; tight lower bound for quantum set disjointness. Fourier transform on {0,1}ⁿ. Polynomial approximation. Dual view of polynomial approximation. Pattern matrices and their spectrum. Complete proof of the pattern matrix method.

Problem Sets

You have 10 days to complete each problem set. Your write-up must be typeset rather than handwritten. I recommend using LaTeX for this purpose. If you are new to LaTeX, you may find it easier to create your document in a user-friendly integrated environment such as Kile or Lyx.

Problem Set I

Problem Set II

Policies

• Attendance and class participation. Attendance and class participation are essential for success in this course. If you must miss class for any reason, please let me know in advance via email. I emphatically welcome questions and any other input from you—your active participation in this course will enhance your learning experience and that of the other students.
• Late submissions. Late work will not be accepted, resulting in zero credit for the corresponding activity.
• Academic honesty. The students are expected to fully abide by UCLA's student conduct policies, including Section 102.01 on academic honesty. You will find a wealth of helpful materials here, including the Student Guide to Academic Integrity. Academic dishonesty will be promptly reported to the Dean of Students' Office for adjudication and disciplinary action. Remember, cheating may have significant and irrevocable consequences for your academic record and professional future. Please do not cheat.