Additive combinatorics with a view towards computer science and cryptography: An exposition

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.

37 pages. In Proceedings of the International Number Theory Conference in Memory of Alf van der Poorten, to appear

References in corpus (11)

• Extremal results in sparse pseudorandom graphs
• Explicit constructions of extractors and expanders
• Structure in additively nonsmoothing sets
• 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
• An additive combinatorics approach to the log-rank conjecture in communication complexity
• A Model Theoretic Proof of Szemerédi's Theorem
• Counting sum-free sets in Abelian groups
• New results for the growth of sets of real numbers