CS 289 Communication Complexity
||Prof. Alexander Sherstov
||my last name at cs.ucla.edu
||MW 2–3:50pm in Boelter 5273
||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. 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).
- 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
- Class participation, 10%. Attendance and
class participation will be graded on a credit/no
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 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
- 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
- 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
- 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.