CS 289 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 for one or two lectures, depending on class size. Preparing the scribe notes will help you internalize the material at a new level. Your scribe notes will be a valuable resource for those who missed class that day and anyone else interested in communication complexity. Please typeset your scribe notes in LaTeX using the instructions and template below. The scribe notes are due one week after the lecture. Please email me a single ZIP archive with all your files (PDF file, LaTeX source file, bibliography file, as well as figure files if any).

  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, academic honesty, and regrade requests.
• Class participation, 10%. Attendance and class participation 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.
   • 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 a week 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 is essential for success in this course. If you are absent without a documented excuse, I will not be able to go over missed lecture material with you. 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. Exceptions to this policy will be granted only when expressly required by UCLA regulations, e.g., in the event of a documented medical excuse.
• 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 will have significant and irrevocable consequences for your academic record and professional future. Please do not cheat.
• Regrade requests. Regrade requests must be made within one week after the graded assignments have been handed out, regardless of whether you attended class that day. Please put your request in writing, indicating the parts you want regraded and why, and hand in your request to me in class or during office hours. As usual, please keep in mind the unlikely but real possibility that a regrade may lower your grade, in case a previously overlooked mistake is discovered.
• Cell phone use. Use of cell phones, laptops, or other electronic devices during class is distracting to the instructor and other students and is forbidden. Please ensure that your phone and any other devices are in silent mode for the duration of class.