Additive Combinatorics and Computer Science.

Mini-Course: August 23-24 at Princeton University (immediately after RANDOM+APPROX 07).

Lecturers: Boaz Barak, Luca Trevisan and Avi Wigderson

Program: The following lectures were given in the course. click here for lecture notes of the course (this the is first draft of the notes - stay tuned for updated versions, in the mean time click here for errata by Rani Hod). (click here for latex template of lecture notes.)

• Introduction and overview / Luca Trevisan

• Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan lecture notes

• The sum-product theorem and its applications / Avi Wigderson powerpoint slides lecture notes

• Proof of the sum-product theorem / Boaz Barak powerpoint slides , (slides with annotations - powerpoint 2007 only) lecture notes

• Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan lecture notes

• Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan lecture notes

• Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan lecture notes

• Applications: Direct Product Theorems / Avi Wigderson lecture notes

• Applications: PCPs and pseudorandomness / Luca Trevisan lecture notes

click here for PDF program and schedule

Synopsis:

Additive combinatorics studies structural properties of subsets of numbers and other Abelian groups. It is concerned with questions such as what conditions on a set A assure that A contains long arithmetic progressions, or what conditions imply that A's sum-set (the set {x+y: x,y in A}) is small or large . Recent years saw both important advances in this field and some computer science applications. This mini course will review both of these from the perspective of theoretical computer science. The course is intended for researchers and students with background in theoretical computer science, but no prior knowledge of additive combinatorics.

Topics will include:

1. Proof of Szemeredi's Theorem on existence of long arithmetic progression in every sufficiently dense set.
2. Gowers uniformity - a higher degree variant of Fourier analysis.
3. Proof of the Bourgain-Katz-Tao finite-field sum product theorem.
4. Applications to property testing and PCP's.
5. Applications to the constructions of randomness extractors.

Organizers: Boaz Barak and Moses Charikar. Email: acminicourse@gmail.com

Links:

• Additive Combinatorics - book by Terence Tao and Van Vu
• Lecture notes on additive combinatorics: Tao Vu Green Gowers
• Structure and Randomness in combinatorics - FOCS 07 tutorial by Terence Tao