Computer Science
Tel-Aviv University

0368-3391-01
Undergraduate Seminar on Communication Complexity

Instructor: Iftach Haitner
Fall  2012

Course Description

The need for communication arises whenever two or more computers, systems or humans need to jointly perform a task that they cannot perform alone. In this course we will study the question of how much communication is necessary to solve a given computational problem. Such questions are of fundamental interest in their own right, and are also increasingly important to the understanding of computational requirements for algorithms for massive data sets, most notably in the streaming model. We will cover selected topics from the text "Communication Complexity" by E. Kushilevitz and N. Nisan. At the end of the semester, if time and interest permits, we will cover papers on recent applications of communication complexity to lower bounds for the streaming model. Students are expected to present a lecture on a section of the book.

Grading

Will be based on the student presentation (including the practice talk) and class participation.  10 point will be taken off for each unjustified absence,  and 5 for an outrages late.  

Prerequisites

Some knowledge of algorithms and basics of probability.

Time and location

The seminar will take place on Thursdays, 10:00-12:00, in Kaplun 324

Text

Communication Complexity by Eyal Kushilevitz and Noam Nisan. (Note useful pointers to errata from Eyal's homepage).

Announcements

Please email me the talk you'd like to give, one speaker per class. A practice talk is mandatory,  typically given one week before the talk (right after the formal talk).

Schedule

  1. October 25: Introduction, course administration
  2. Nov 1: Introduction to communication complexity. [KN] Chapter 1.1 Elad Cochavi
  3. Nov 8: Rectangles. [KN] Chapter 1.2.  Shalev ?
  4. Nov 15: Fooling sets and rectangle size. Rank lower bounds. [KN] Chapter 1.3, 1.4. Ran Pollak
  5. Nov 22: Randomization. Reading. [KN] Chapter 3.1,3.2.  Shay Weiss
  6. Nov 29: : Variable Partition Models. [KN] Chapter 7.1 -7.3 Daniel Solomon
  7. Dec 6: Bisection width of networks. Lower bounds for VLSI.  [KN] Chapter 8.1,8.3. Yevgeni Groisman
  8. Dec 13: Decision trees and data structures. Reading: [KN] Chapter 4.3, 9.1 -9.3 Amit Goldfarb
  9. Dec 20: The streaming model I. Estimating the number of distinct elements in a stream. Reading: Based on Lecture 1 of Piotr Indyk's Fall 2007 course and the first lecture of his Spring 2009 course . Idan Shabat
  10. Dec 27: The streaming model II. Estimating the L2 norm via Alon-Matias-Szegedy. Reading: Based on first 15 slides of Lecture 2. of Piotr Indyk's Fall 2007 and Spring 2009 course. See also the AMS paper. Dean Doron
  11. Jan 3: The streaming model III. Lower bounds via communication complexity. Reading: Henzinger, Raghavan, Rajagopalan, "Computing on data streams".  Rom Carmel
  12. Jan 10:?
  13. Jan 17:?