We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [Geom. Funct. Anal. 2010], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and $L^p$-norm free) point of view, which allows for proofs to easily be converted to probabilistic algorithms that decide membership in almost-periodic sumsets of dense subsets of $GF(2^n)$.

As an application, we give a new algorithmic version of the quasipolynomial Bogolyubov-Ruzsa lemma recently proved by Sanders [Anal. PDE 2010]. Together with the results by the last two authors [FOCS 2011], this implies an algorithmic version of the quadratic Goldreich-Levin theorem in which the number of terms in the quadratic Fourier decomposition of a given function is quasipolynomial in the error parameter $\epsilon$, compared with an exponential dependence previously proved by the authors. It also improves the running time of the algorithm to have quasipolynomial dependence on $\epsilon$ instead of an exponential one.

We also give an application to the problem of finding large subspaces in sumsets of dense sets. Green showed in [Surveys in combinatorics 2005] that the sumset of a dense subset of $GF(2^n)$ contains a large subspace. Using Fourier analytic methods, Sanders [Acta Arith. 2011] proved that such a subspace must have dimension $\Omega(\alpha n)$. We provide an alternative (and $L^p$ norm-free) proof of a comparable bound, which is analogous
to a recent result of Croot, Laba and Sisask [arxiv.org 2011] in the integers.

Modified the introduction and organization of the paper. All claims remain unchanged.

We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [Geom. Funct. Anal. 2010], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and $L^p$-norm free) point of view, which allows for proofs to easily be converted to probabilistic algorithms that decide membership in almost-periodic sumsets of dense subsets of $GF(2^n)$.

As an application, we give a new algorithmic version of the quasipolynomial Bogolyubov-Ruzsa lemma recently proved by Sanders [Anal. PDE 2010]. Together with the results by the last two authors [FOCS 2011], this implies an algorithmic version of the quadratic Goldreich-Levin theorem in which the number of terms in the quadratic Fourier decomposition of a given function is quasipolynomial in the error parameter $\epsilon$, compared with an exponential dependence previously proved by the authors. It also improves the running time of the algorithm to have quasipolynomial dependence on $\epsilon$ instead of an exponential one.

We also give an application to the problem of finding large subspaces in sumsets of dense sets. Green showed in [Surveys in combinatorics 2005] that the sumset of a dense subset of $GF(2^n)$ contains a large subspace. Using Fourier analytic methods, Sanders [Acta Arith. 2011] proved that such a subspace must have dimension $\Omega(\alpha n)$. We provide an alternative (and $L^p$ norm-free) proof of a comparable bound, which is analogous
to a recent result of Croot, Laba and Sisask [arxiv.org 2011] in the integers.

Modified the structure and organization of Section 4.2. The main theorem in this section (Theorem 4.8.) remains unchanged.

We give new combinatorial proofs of known almost-periodicity results for sumsets of sets with small doubling in the spirit of Croot and Sisask [Geom. Funct. Anal. 2010], whose almost-periodicity lemma has had far-reaching implications in additive combinatorics. We provide an alternative (and $L^p$-norm free) point of view, which allows for proofs to easily be converted to probabilistic algorithms that decide membership in almost-periodic sumsets of dense subsets of $GF(2^n)$.

As an application, we give a new algorithmic version of the quasipolynomial Bogolyubov-Ruzsa lemma recently proved by Sanders [Anal. PDE 2010]. Together with the results by the last two authors [FOCS 2011], this implies an algorithmic version of the quadratic Goldreich-Levin theorem in which the number of terms in the quadratic Fourier decomposition of a given function is quasipolynomial in the error parameter $\epsilon$, compared with an exponential dependence previously proved by the authors. It also improves the running time of the algorithm to have quasipolynomial dependence on $\epsilon$ instead of an exponential one.

We also give an application to the problem of finding large subspaces in sumsets of dense sets. Green showed in [Surveys in combinatorics 2005] that the sumset of a dense subset of $GF(2^n)$ contains a large subspace. Using Fourier analytic methods, Sanders [Acta Arith. 2011] proved that such a subspace must have dimension $\Omega(\alpha n)$. We provide an alternative (and $L^p$ norm-free) proof of a comparable bound, which is analogous
to a recent result of Croot, Laba and Sisask [arxiv.org 2011] in the integers.