Videos

Applications of additive combinatorics in theoretical computer science

Presenter
March 14, 2014
Abstract
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.
Supplementary Materials