Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Revision(s):

Revision #2 to TR12-135 | 17th April 2013 20:12

Sampling-based proofs of almost-periodicity results and algorithmic applications

Revision #2
Authors: Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf
Accepted on: 17th April 2013 20:12
Keywords:

Abstract:

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.

Changes to previous version:

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

Revision #1 to TR12-135 | 11th November 2012 13:04

Sampling-based proofs of almost-periodicity results and algorithmic applications

Revision #1
Authors: Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf
Accepted on: 11th November 2012 13:04
Keywords:

Abstract:

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.

Changes to previous version:

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

Paper:

TR12-135 | 26th October 2012 05:06

Sampling-based proofs of almost-periodicity results and algorithmic applications

TR12-135
Authors: Eli Ben-Sasson, Noga Ron-Zewi, Madhur Tulsiani, Julia Wolf
Publication: 26th October 2012 05:06
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint