Course Description

We shall explore a collection of recent research in computer science that has benefited from the use of (variants of)  techniques from information theory.

During the quarter, each of these phrases will be uttered with positive probability:
  • Data structure lowerbounds
  • Communication complexity lowerbounds
  • Compression
  • Data stream lowerbounds
  • Gap amplification (strengthening the PCP theorem).
  • Pseudorandom Generators
  • Extractors

The course will be organized as follows:
  • Each student will pick a paper from the paper list that she/he would like to present in the class.

  • Anup will lecture in the first 4 or 5 weeks.

  • The remainder of the class will be organized into a segment on communication complexity, a segment on data structure lowerbounds and a segment on pseudorandomness, with student presentations covering some recent important results from these areas.

The goal of the course is to immerse ourselves in each of these exciting research areas, and start thinking about open problems.


Students will be graded on homework, participation in generating lecture notes, and paper presentations.


“Elements of Information Theory”, Cover and Thomas. The two surveys listed at the bottom of this page will be very relevant.

Class Mailing List:

Those enrolled in the class should be automatically subscribed to the class list:

Others are welcome to subscribe to the list here.

Course Requirements:

Mathematical maturity and a basic background in theoretical computer science.

Two Useful Surveys

PostScript file icon grams.ps409K Download Graph Entropy, by Gabor Simonyi
Adobe Acrobat file icon EntropyAndCounting.pdf238K Download View Entropy and Counting by Jaikumar Radhakrishnan
Send questions about this workspace to Anup Rao.