Additive Combinatorics and Theoretical Computer Science

Additive combinatorics is the branch of combinatorics where the objects of study are subsets of the integers or of other abelian groups, and one is interested in properties and patterns that can be expressed in terms of linear equations. More generally, arithmetic combinatorics deals with properties and patterns that can be expressed via additions and multiplications. In the past ten years, additive and arithmetic combinatorics have been extremely successful areas of mathematics, featuring a convergence of techniques from graph theory, analysis and ergodic theory. They have helped prove long-standing open questions in additive number theory, and they offer much promise of future progress. Techniques from additive and arithmetic combinatorics have found several applications in computer science too, to property testing, pseudorandomness, PCP constructions, lower bounds, and extractor constructions. Typically, whenever a technique from additive or arithmetic combinatorics becomes understood by computer scientists, it finds some application. Considering that there is still a lot of additive and arithmetic combinatorics that computer scientists do not understand (and, the field being very active, even more will be developed in the near future), there seems to be much potential for future connections and applications. 1