CS 289 Communication Complexity

Course 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.

Tentative topics include: the basic two-party communication model; equivalence of deterministic and nondeterministic communication; randomization; geometry of communication and dual methods for proving communication lower bounds; multiparty communication; unbounded-error communication; quantum communication; applications of communication to computational learning, circuit lower bounds, and streaming algorithms. The course will emphasize proof techniques for communication lower bounds, illustrated on concrete communication problems. 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 send me your .pdf file and the source files (.tex and .bib, as well as figure files if any) in an email message.

Instructions

Template

Problem sets I and II, 30% each. 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, with the essential difference that you are allowed to collaborate on the problems. Please see below for important policies, including academic honesty, collaboration statements, late submissions, and regrade requests.

Class participation, 10%. Attendance and class participation will be graded on a credit/no credit basis individually for every lecture. The class participation grade for the course will be computed by averaging these binary scores over all lectures.

Lecture Notes

The lecture notes will be posted here as the course progresses. Disclaimer: the lecture notes have been prepared by student scribes and are posted here as is, with little or no editing on my part. If you notice any errors or omissions, please let me know.

1	Deterministic communication Course overview. Deterministic model of two-party communication. Protocols for the equality, parity, average, and median problems. Formal definition of protocols and their tree representation. Combinatorial rectangles; a global and local definition and their equivalence.
2	Lower bounds for deterministic communication Protocol-induced partitions of the input space into rectangles. Fooling sets. Generalization of fooling sets to measure arguments; rectangle size bounds. Tight lower bounds for the equality, disjointness, greater-than, and inner product functions; alternate proofs using fooling sets and rectangle size bounds.
3	Matrix rank in communication complexity Rank of Boolean matrices over R versus arbitrary fields; an exponential separation. Lower bounds on communication via matrix rank; equality, greater-than, inner product, and disjointness functions. Upper bounds on communication in terms of rank. Lower bounds via rank versus fooling sets; an exponential separation for inner product. Random Boolean matrices have small fooling sets.
4	Partitions and covers Protocol covers, partitions, and covers. An equivalence of deterministic communication and protocol covers. Small covers give efficient deterministic protocols. A near-tight characterization of cover size via the rectangle size method; analysis of the gap using the equality function.
5	Nondeterminism Deterministic communication complexity and cover size of random functions. Proof systems; equivalence to covers. Nondeterminism as a proof system or cover. Relations between deterministic and nondeterministic complexity; examples and separations. Log-rank conjecture; a polynomial separation between the logarithm of the rank and deterministic communication complexity. Nondeterministic and co-nondeterministic complexity of k-disjointness.
6	Polynomial hierarchy and randomization Deterministic lower bound for k-disjointness; a quadratic separation of deterministic and nondeterministic communication complexity. Communication complexity classes Pcc, NPcc, coNPcc, polynomial hierarchy. Reductions. Completeness of disjointness for coNPcc. Introduction to randomized communication. Boosting accuracy via repetition. Randomized protocol for equality.
7	Communication with shared randomness Simulation of randomized protocols by deterministic ones with exponential slowdown; optimality for the equality problem. Public-coin randomized model. Equivalence of private-coin and public-coin models up to a small additive term. Constant-cost protocol for equality, cost-O(k) protocol for k-disjointness, cost-O(log2 n) protocol for greater-than.
8	The minimax theorem Noisy comparison trees. An O(log n)-cost randomized protocol for greater-than; a matching lower bound. Topology of Euclidean space; bounded, closed, convex, and compact sets. Separating hyperplane theorem for a compact and a bounded set. Zero-sum games. Minimax theorem for zero-sum games.
9	Distributional complexity Motivation and examples of convex relaxations. Separating hyperplane theorem for arbitrary convex sets. Distributional communication complexity. Yao's minimax theorem for public-coin randomized communication complexity.
10	Convex relaxations of randomization Geometric view of computation. Lower bounds as search for a separating hyperplane. Convex relaxation of randomized communication as the convex hull of rectangles and their negations. Definition of discrepancy. Discrepancy method. Generalized discrepancy method.
11	More on discrepancy Discrepancy as a characterization of cost-2 protocols. Alternate definitions of discrepancy. Cauchy-Schwarz style analysis of discrepancy. Discrepancy of random functions and inner product. Linear lower bounds on the randomized communication complexity of random functions and inner product. Limitations of the discrepancy method; relation to nondeterminism. Corruption bound.
12	Complexity of set disjointness Linear lower bound on the randomized communication complexity of set disjointness. Sipser-Gács theorem. Complete picture of the relations among Pcc, NPcc, coNPcc, BPPcc, and the polynomial hierarchy.
13	Spectral properties of matrices Singular value decomposition; existence and uniqueness. Minimax characterization of the singular values. Orthogonal diagonalization of symmetric matrices. Positive semidefinite and positive definite matrices; definition and alternate characterizations. Matrix norms. Frobenius norm, spectral norm, trace norm; characterization in terms of singular values.
14	Gap Hamming distance Talagrand's concentration inequality. Sharp concentration of the distance of a random Boolean vector from a given linear subspace. Gap Hamming distance and gap orthogonality problems; sampling-based communication protocols and matching lower bounds on communication.
15	Unbounded-error communication Unbounded-error complexity as the limit of private-coin randomized communication complexity with error ε as ε→1/2. Importance of private randomness; a cost-2 protocol for every function in the public-coin model. Sign-rank; equivalence to unbounded-error complexity. Arbitrarily large gaps between rank and sign-rank. Isotropic position. Forster's theorem. Linear lower bound on the unbounded-error complexity of inner product.
16	Norms in communication complexity 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 μ, ν, γ2. Grothendieck's inequality. Proof of Grothendieck's inequality due to Rietz. Equivalence of μ, ν, γ2 up to small constant factors.
17	Quantum communication Quantum computing. Circuit view of communication. Definitions of quantum communication in terms of circuits and matrix analysis. Convex relaxation of quantum communication in terms of the γ2 norm. Lower bounds on quantum communication via discrepancy and generalized discrepancy. Pattern matrix method (part 1/2). Statement of the method; tight lower bound for set disjointness. Background for the pattern matrix method: approximation by polynomials, Fourier transform.
18	Multiparty communication Pattern matrix method (part 2/2): dual view of polynomial approximation; pattern matrices and their singular values; complete proof of the pattern matrix method. Multiparty communication. Number-on-the-forehead model; motivation. Grolmusz's protocol for symmetric functions. Course wrap-up.

Problem Sets

You will have ten days to complete each problem set. You are allowed to collaborate with other students on Problem Set I but must write up the solutions on your own. Searching for or consulting solutions to similar problems is expressly forbidden since it detracts from the pedagogical value of the assignment. The write-ups must be typeset rather than handwritten; doing so primes you to write clearly and concisely and take pride in your work. LaTeX is recommended for this purpose, being the standard typesetting software in the research community. Please see below for other policies, including collaboration statements, academic honesty, and late submissions.

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 during office hours or over email. I emphatically welcome questions during lecture and any other input from you—your active participation in this course will enhance your own learning experience and that of the other students.

Late submissions. Late submissions and scribe notes will not be accepted, resulting in zero credit for the corresponding activity. Exceptions to this policy will only be granted when expressly required by UCLA regulations, e.g., in the event of a documented medical emergency. The students are asked to report to class on time. Late arrivals will count as an absence, with zero credit for class participation on that day.

Academic honesty. The students are expected to fully abide by UCLA's student conduct policies, including Section 102.01 on academic honesty. When working on a problem set, the students are not allowed to consult solutions to similar problems on the Internet or in print because doing so greatly diminishes the course's pedagogical value.

Collaboration. Collaboration on Problem Set I is allowed. However, the students must write up their solutions individually, without consulting anyone else's write-ups. Every write-up must be accompanied by a collaboration statement, listing any collaborators and their respective contributions. If the student did not collaborate with anyone on a given assignment, that fact must also be expressly stated.

Regrade requests. Requests for a regrade must be made no later than one week after the graded assignments have been handed out in class, regardless of whether you attended class that day. Please put your request in writing, indicating the parts you want regraded and why, and hand your request to me in person. 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.