Lower Bounds and Information Theory (Q2, 2010) -- Course webpage

Course Description

This course will concentrate on two related subjects: Lower Bounds and Information Theory. The main thread of the course will be data structure and streaming lower bounds, and how direct sum results (existing or conjectured) come into play; but we will discuss many other topics that touch these two areas.

The course is at the level of graduate students with some mathematical maturity.

The first lecture will be about the round elimination lemma (including its information-theoretic proof), about other direct sum theorems and conjectures (in communication complexity and elsewhere) and about their applications for lower bounds (in data structures, streaming, and other topics).

The other lectures will mostly be chosen among the following topics:

* more on communication complexity: proof techniques, classical results and applications

* various data structure lower bounds based on communication complexity (in particular Patrascu-type lower bounds based on LSD)

* other uses of information theory in lower bounds and in impossibility proofs (including in cryptography)

* encoding-based proofs (e.g. Moser's constructive Lovasz Local Lemma, but also some encoding based proofs of Patrascu, and classical results from the Kolmogorov complexity literature)

* methodological comments on lower bounds

* other topics in data structure lower bounds (the chronogram method, succinct data structure lower bounds, lower bounds with assumptions or restrictions, certificate complexity)

* parallel repetition lemmas, and information-theoretic aspects in their proofs

* streaming complexity of edit distance and other complex metrics

* The icost method and its geometrical aspects

* circuit lower bounds for low-depth circuits

* analysis of Boolean functions and its use in data structure and streaming lower bounds, as well as in hardness of approximation

* learning theory from the lower bounds perspective, the SQ-model and VC-dimension.

* pseudorandomness and its connection to hardness

There is no textbook for the course (in fact, many of the topics are not covered in books at all), but an effort will be made to point to easy-to-read sources on the subject matter (e.g. lecture notes online) and not only to research papers.

The goal of the course is to paint the current landscape in lower bounds research (to the best of the lecturer's ability) and to provide background for active work on lower bounds (in multiple areas). Therefore an attempt is made to show techniques and principles with as wide an applicability as possible, and show their simplest invocations.

Course Details

Literature: Ad-hoc.

Lecturer: Elad Verbin
Course Language: English
Credits: 5 ECTS points
Quarter: 2nd (Fall 2010)
Prerequisites: Algorithms and Data Structures
Evalution: Based on attendance and a project, pass/fail.

Room: Lecture room 120 in the Incuba Science Park, Åbogade 15

Time: Thursdays, 9:15-12

Lecture Plans:

Lecture 1:

Introduction to communication complexity

Introduction to information theory

The Round Elimination Lemma (REL) – complete proof, based on Pranab Sen’s proof

Application of REL to Greater Than lower bound,

Application of REL-type idea to Viola-Wigderson lower bound on NOF Pointer Chasing

Lecture 2:

Finish Proof of REL lower bound

Application of REL to Data Structure lower bounds (Miltersen et al)

Pass Elimination Lemma (in streaming)

Application of REL-type ideas to succinct lower bounds (in indexing model)

Lecture 3:

Chronogram-based lower bounds for prefix-sum, and why they are similar to REL

Other direct sum ideas.

Brody et al. style Round Elimiation

Round Elimination with overlapping inputs: a challenge.

Patrascu’s conjecture

Some questions which might be solved this way: Routing; NOF pointer chasing

Lecture 4:

Direct Product. In particular, Drucker’s Direct Product Theorem

Lecture 5:

Monotone Circuit lower bounds: Lower bound on S-T-connectivity, through FORK problem

Lecture 6:

Expanders and the Zig-Zag Product. Information theoretic concepts behind the (algebraic) proof.

Lecture 7:

Parallel Repetition: Positive Results and Negative Result. Stressing information-theoretic aspects of the proof.