Theory of Computing Library Graduate Surveys
---------------------------------------------------
Title : Additive Combinatorics and its Applications in Theoretical Computer Science
Authors : Shachar Lovett
Number : 8
Pages : 1-55
URL : http://www.theoryofcomputing.org/articles/gs008
Abstract
--------
Additive combinatorics (or perhaps more accurately, arithmetic
combinatorics) is a branch of mathematics which lies at the
intersection of combinatorics, number theory, Fourier analysis and
ergodic theory. It studies approximate notions of various algebraic
structures, such as vector spaces or fields. In recent years, several
connections between additive combinatorics and theoretical computer
science have been discovered. Techniques and results from additive
combinatorics have been applied to problems in coding theory, property
testing, hardness of approximation, computational complexity,
communication complexity, randomness extraction and pseudo-randomness.
The goal of this survey is to provide an introduction to additive
combinatorics for students and researchers in theoretical computer
science, to illustrate some of the exciting connections to classical
problems in theoretical computer science, and to describe the many
open problems that remain.