Professor: |
Alexander Sherstov | |

Email: |
my last name @cs.ucla.edu | |

Quarter: |
Winter 2012 | |

Room: |
5273 Boelter Hall | |

Time: |
Monday and Wednesday 4-5:50pm | |

Office Hours: |
3731J Boelter Hall, Wednesday 2-3pm | |

Webpage: |
http://www.cs.ucla.edu/~sherstov/teaching/2012-winter | |

Textbook: |
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
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.

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

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.

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 |

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