Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR10-010 | 16th January 2010 20:16

Equivalence of polynomial conjectures in additive combinatorics

RSS-Feed




TR10-010
Authors: Shachar Lovett
Publication: 16th January 2010 22:29
Downloads: 3584
Keywords: 


Abstract:

We study two conjectures in additive combinatorics. The first is the polynomial Freiman-Ruzsa conjecture, which relates to the structure of sets with small doubling. The second is the inverse Gowers conjecture for $U^ $, which relates to functions which locally look like quadratics. In both cases a weak form, with exponential decay of parameters is known, and a strong form with only a polynomial loss of parameters is conjectured. Our main result is that the two conjectures are in fact equivalent.



ISSN 1433-8092 | Imprint