Additive Combinatorics and Computer Science.
Mini-Course: August 23-24 at Princeton University (immediately after RANDOM+APPROX 07).
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
- 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:
- Proof of Szemeredi's Theorem on existence of long arithmetic progression in every sufficiently dense set.
- Gowers uniformity - a higher degree variant of Fourier analysis.
- Proof of the Bourgain-Katz-Tao finite-field sum product theorem.
- Applications to property testing and PCP's.
- Applications to the constructions of randomness extractors.
Organizers: Boaz Barak and Moses Charikar. Email: acminicourse@gmail.com
Links: