pdf icon
Theory of Computing Library
Graduate Surveys 8
Additive Combinatorics and its Applications in Theoretical Computer Science
Published: September 26, 2017    (55 pages)
Download article from ToC site:
[PDF (463K)] [PS (3240K)] [Source ZIP]
Keywords: additive combinatorics, theoretical computer science
ACM Classification: F.2.2, G.2.3
AMS Classification: 68Q17, 68Q25

Abstract: [Plain Text Version]

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.