CS 289 Communication Complexity
||Prof. Alexander Sherstov
||my last name at cs.ucla.edu
||MW 2–3:50pm in MS 3915D
||MW 1:30–2pm in Boelter 3731J
||E. Kushilevitz and N. Nisan, Communication Complexity, Cambridge University Press, 2nd edition, 2006.
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
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.
- 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. At the beginning of every lecture, I will ask for
a volunteer to be the scribe, or designate one if no
one volunteers. 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.
More precisely, scribe notes for a Monday lecture are
due at 2pm the following Monday, and similarly scribe
notes for a Wednesday lecture are due at 2pm the
following Wednesday (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.
- 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.
The course schedule below is tentative and may be
adjusted in response to student interest and time
- 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.
- 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
- 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.
- 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,
protocol for greater-than. Noisy comparison
trees. O(log n) randomized
protocol for greater-than; matching lower
- 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
- 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
- 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.
- 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
- 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
- Unbounded-error communication.
Unbounded-error communication as the limit of
private-coin randomized communication with
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.
- 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 μ, ν,
γ2 up to small constant
- 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
γ2 norm. Lower bounds
on quantum communication via discrepancy and
- Pattern matrix method. Statement of
the method; tight lower bound for quantum set
disjointness. Fourier transform on
approximation. Dual view of polynomial
approximation. Pattern matrices and their
spectrum. Complete proof of the pattern matrix
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
- Attendance and class participation.
Attendance and class participation are essential for success in this course.
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
- Late submissions. Late work will not be
accepted, resulting in zero credit for the
- 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.