Additive combinatorics with a view towards computer science and cryptography: An exposition
arXiv:1108.3790
Abstract
Recently, additive combinatorics has blossomed into a vibrant area in mathematical sciences. But it seems to be a difficult area to define - perhaps because of a blend of ideas and techniques from several seemingly unrelated contexts which are used there. One might say that additive combinatorics is a branch of mathematics concerning the study of combinatorial properties of algebraic objects, for instance, Abelian groups, rings, or fields. This emerging field has seen tremendous advances over the last few years, and has recently become a focus of attention among both mathematicians and computer scientists. This fascinating area has been enriched by its formidable links to combinatorics, number theory, harmonic analysis, ergodic theory, and some other branches; all deeply cross-fertilize each other, holding great promise for all of them! In this exposition, we attempt to provide an overview of some breakthroughs in this field, together with a number of seminal applications to sundry parts of mathematics and some other disciplines, with emphasis on computer science and cryptography.
arXiv comment37 pages. In Proceedings of the International Number Theory Conference in Memory of Alf van der Poorten, to appear
References in corpus (27)
- Random matrices: Universality of local eigenvalue statistics up to the edge
- The critical probability for random Voronoi percolation in the plane is 1/2
- On the Bogolyubov-Ruzsa lemma
- The primes contain arbitrarily long polynomial progressions
- From rotating needles to stability of waves; emerging connections between combinatorics, analysis and PDE
- Arithmetic progressions in sets of fractional dimension
- Sumset and inverse sumset theorems for Shannon entropy
- Linear forms and higher-degree uniformity for functions on
- Extremal results in sparse pseudorandom graphs
- Higher correlations of divisor sums related to primes III: k-correlations
- Explicit constructions of extractors and expanders
- An equivalence between inverse sumset theorems and inverse conjectures for the U^3 norm
- The dichotomy between structure and randomness, arithmetic progressions, and the primes
- Combinatorial theorems in sparse random sets
- Translation invariant equations and the method of Sanders
- Structure in additively nonsmoothing sets
- A point of view on Gowers uniformity norms
- On Congruences with Products of Variables from Short Intervals and Applications
- Points on curves in small boxes en applications
- The structure of approximate groups
- Roth's theorem in many variables
- A Model Theoretic Proof of Szemerédi's Theorem
- An additive combinatorics approach to the log-rank conjecture in communication complexity
- Inverse Additive Problems for Minkowski Sumsets II
- Counting sum-free sets in Abelian groups
- New results for the growth of sets of real numbers
- Solymosi's multiplicative energy bound for complex numbers