Applications of additive combinatorics in theoretical computer science

Shachar Lovett
University of California, San Diego (UCSD)

Additive combinatorics studies subsets of algebraic structures, and relations between various notions of structure and randomness for these objects. It has been an influential tool in number theory and discrete geometry for several decades. Recently, additive combinatorics has also become influential in theoretical computer science, with applications in computational complexity, communication complexity, randomness extraction, sub-linear algorithms, cryptography and coding theory. I will discuss some of these applications, and the many intriguing open problems and research directions that emerge from these works.

Presentation (PDF File)

Back to Combinatorial and Computational Geometry: Tutorials