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 Lp-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(2n).

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 , compared with an exponential dependence previously proved by the authors. It also improves the running time of the algorithm to have quasipolynomial dependence on 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(2n) contains a large subspace. Using Fourier analytic methods, Sanders [Acta Arith. 2011] proved that such a subspace must have dimension (n). We provide an alternative (and Lp norm-free) proof of a comparable bound, which is analogousto a recent result of Croot, Laba and Sisask [arxiv.org 2011] in the integers.