Additive Combinatorics and Computer Science.
Mini-Course: August 23-24 at Princeton University (immediately after RANDOM+APPROX 07).
Registration: Registration to the mini-course is FREE but you need to register by August 1st, 2007. Registration web page will be reachable through this site by June 8th, 2007.
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.
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
Links: