Main»Additive Combinatorics Minicourse

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
Video (Real media: low res, high res)
  • Szemeredi regularity lemma and Szemeredi's theorem for k=3 / Luca Trevisan lecture notes
Video (Real media: low res, high res)
Video (Real media: low res, high res)
Video (Real media: low res, high res)
  • Proof of the regularity lemma (original plan: applications to property testing) / Luca Trevisan lecture notes
Video (Real media: low res, high res)
  • Szemeredi's theorem for k=3: Roth's proof / Luca Trevisan lecture notes
Video (Real media: low res, high res)
  • Gowers uniformity norms and sketch of Gowers' proof of Szemeredi's theorem / Luca Trevisan lecture notes
Video (Real media: low res, high res)
  • Applications: Direct Product Theorems / Avi Wigderson lecture notes
Video (Real media: low res, high res)
  • Applications: PCPs and pseudorandomness / Luca Trevisan lecture notes
Video (Real media: low res, high res)

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: