Sampling-Based Proofs of Almost-Periodicity Results and Algorithmic Applications

We give new and simple combinatorial proofs of almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [7], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative point of view which relies only on Chernoff’s bound for sampling, and avoids the need for L p -norm estimates used in the original proof of Croot and Sisask.

• Publication year

  2012

• Venue

  International Colloquium on Automata, Languages and Programming

• Publication date

  2012-10-25

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1007/978-3-662-43948-7_79arXiv 1210.6917
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• An analog of Freiman's theorem in groups

  2018cited by this paper
• An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem

  2015cited by this paper
• New bounds for matching vector families

  2012cited by this paper
• An Additive Combinatorics Approach Relating Rank to Communication Complexity

  2012cited by this paper
• An Entropic Proof of Chang's Inequality

  2012cited by this paper
• Quadratic Goldreich-Levin Theorems

  2011cited by this paper
• From affine to two-source extractors via approximate duality

  2011cited by this paper
• Higher-Order Fourier Analysis Of $${\mathbb{F}_{p}^n}$$ And The Complexity Of Systems Of Linear Forms

  2011cited by this paper
• Arithmetic Progressions in Sumsets and Lp-Almost-Periodicity

  2011cited by this paper
• Linear forms and quadratic uniformity for functions on ℤN

  2010cited by this paper
• A Fourier-Analytic Approach to Reed–Muller Decoding

  2010cited by this paper
• A Probabilistic Technique for Finding Almost-Periods of Convolutions

  2010cited by this paper
• On the structure of steps of three‐term arithmetic progressions in a dense set of integers

  2010cited by this paper
• On Roth's theorem on progressions

  2010cited by this paper
• Green's sumset problem at density one half

  2010cited by this paper
• On the Bogolyubov–Ruzsa lemma

  2010cited by this paper
• Regularity, Boosting, and Efficiently Simulating Every High-Entropy Distribution

  2009cited by this paper
• List-decoding reed-muller codes over small fields

  2008cited by this paper
• AN INVERSE THEOREM FOR THE GOWERS $U^3(G)$ NORM

  2008cited by this paper
• Montréal notes on quadratic Fourier analysis

  2007cited by this paper
• The true complexity of a system of linear equations

  2007cited by this paper
• Additive Combinatorics: Long arithmetic progressions in sum sets

  2006cited by this paper
• Additive structures in sumsets

  2006cited by this paper
• Low-degree tests at large distances

  2006cited by this paper
• Gowers uniformity, influence of variables, and PCPs

  2005cited by this paper
• Finite field models in additive combinatorics

  2004cited by this paper
• Finite field models in additive combinatories

  2004cited by this paper
• A polynomial bound in Freiman's theorem

  2002cited by this paper
• Quick Approximation to Matrices and Applications

  1999cited by this paper
• A New Proof of Szemerédi's Theorem for Arithmetic Progressions of Length Four

  1998cited by this paper
• Arithmetic progressions in sumsets

  1991cited by this paper
• A hard-core predicate for all one-way functions

  1989cited by this paper

• Classical and Quantum Polynomial Freiman-Ruzsa Algorithms

  2026cites this paper
• Algorithmic Polynomial Freiman-Ruzsa Theorems

  2025cites this paper
• A near-optimal Quadratic Goldreich-Levin algorithm

  2025influential citation
• Structure of sparse Boolean functions over Abelian groups, and its application to testing

  2024cites this paper
• Worst-case to average-case reductions via additive combinatorics

  2022cites this paper
• Cubic Goldreich-Levin

  2022cites this paper
• Extractors for sum of two sources

  2021cites this paper
• Tight Chang's-lemma-type bounds for Boolean functions

  2020cites this paper
• Almost periodicity and its applications to Roth’s theorem

  2020cites this paper
• Approximate Local Decoding of Cubic Reed-Muller Codes Beyond the List Decoding Radius

  2018cites this paper
• Parity Decision Tree Complexity and 4-Party Communication Complexity of XOR-functions Are Polynomially Equivalent

  2015cites this paper
• Finite field models in arithmetic combinatorics - ten years on

  2015cites this paper
• J. (2015). Finite field models in arithmetic combinatorics – ten years on. Finite Fields and Their Applications , 32 , 233-274.

  2014cites this paper
• NOTES ON THE CROOT-SISASK LEMMA

  2013cites this paper