Advanced Topics in Complexity - Spring 2002

Dr. Amos Beimel

This course will mainly discuss communication complexity. The scenario is seemingly simple: There are two players Alice who holds an n bit string x and Bob who holds an n bit string y. Their goal is to compute the value of some function f(x,y). Clearly, Alice can send her input to Bob who will compute f(x,y). The question we will consider is for which functions there exists protocols with less communication. We consider three types of protocols, deterministic, nondeterministic, and randomized. For example, if Alice and Bob want to check if x=y (e.g., they hold two copies of a big database and want to check if the copies are identical), then any deterministic protocol requires n bits of communication, while randomized protocols require only log n bits. We use the results on communication complexity to prove lower bounds for other areas of computer science where communication is involved explicitly or implicitly, such as Boolean circuits, decision trees, and VLSI chips.

If time will permit we will also discuss other lower bounds for Boolean circuits (e.g., AC0 circuits and monotone circuits).

Syllabus:

  1. Two party communication complexity, upper and lower bounds:
  2. Applications for proving lower bounds for VLSI chips, decision trees, and data structures.
  3. Communication complexity of relations, application for lower bounds for monotone circuits depth and formulae size.
  4. Lower bounds for AC0 circuits.

Requirements:

The course is an elective course for graduate students. This is a 2-credit course, consisting of one weekly meeting. The grade will be based on 2-4 homework assignments.
Prerequisite Course: Computational Complexity - 202-2-1111. Good students without the prerequisite who want to join the course can speak to me.

Book:

Lectures:

All chapters refer to the above book.

Num. Topic Date Handouts,
exercises
textbook
1 Introduction. 11.3.02 Announcement  
2 Deterministic Protocols. 18.3.02   1.1-1.3
3 The rank lower bound.
Non-Deterministic Protocols.
8.4.02 Ex. 1 (ps), (pdf) 1.4
2.1
4 On Partitions and Covers. 15.4.02   2.3
5 More on Partitions and Covers. 15.4.02   2.2
6 Randomized protocols. 29.4.02   3.1,3.2,3,4
7 Chernoff Bound.
Randomized protocols with public coins.
6.5.02 Ex. 2 (ps), (pdf) 3.3
8 Lower bounds on Randomized protocols. 12.5.02   3.5
9 Best and Worst partition communication complexity.
Lower bounds for VLSI circuits and Decision trees.
13.5.02   7.1-7.2
8.3,9.1
10 Depth of Boolean circuits and communication complexity. 19.5.02   10.1-10.2,
5. 1 (partially)
11 Depth of monotone Boolean circuits.
Lower bounds for s-t-CON.
20.5.02   10.3
12 Lower bounds for the relation FORK. 26.5.02   5.3

Information:

Lectures hours: Monday 14:00-16:00.
Reception hours: Tuesday 16-18, Building 58 (Math and CS), Room 205.
E-mail: beimel at cs.bgu.ac.il
Phone: 647 7858

Some Links:

  1. A survey on communication complexity by Eyal Kushilevitz.