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