ECCC-Report TR12-135https://eccc.weizmann.ac.il/report/2012/135Comments and Revisions published for TR12-135en-usWed, 17 Apr 2013 20:12:01 +0300
Revision 2
| Sampling-based proofs of almost-periodicity results and algorithmic applications |
Eli Ben-Sasson,
Noga Ron-Zewi,
Madhur Tulsiani,
Julia Wolf
https://eccc.weizmann.ac.il/report/2012/135#revision2We 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.
Wed, 17 Apr 2013 20:12:01 +0300https://eccc.weizmann.ac.il/report/2012/135#revision2
Revision 1
| Sampling-based proofs of almost-periodicity results and algorithmic applications |
Eli Ben-Sasson,
Noga Ron-Zewi,
Madhur Tulsiani,
Julia Wolf
https://eccc.weizmann.ac.il/report/2012/135#revision1We 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.
Sun, 11 Nov 2012 13:04:06 +0200https://eccc.weizmann.ac.il/report/2012/135#revision1
Paper TR12-135
| Sampling-based proofs of almost-periodicity results and algorithmic applications |
Eli Ben-Sasson,
Noga Ron-Zewi,
Madhur Tulsiani,
Julia Wolf
https://eccc.weizmann.ac.il/report/2012/135We 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.
Fri, 26 Oct 2012 05:06:42 +0200https://eccc.weizmann.ac.il/report/2012/135