ECCC
Electronic Colloquium on Computational Complexity
Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR12-029 | 3rd April 2012 23:57

An exposition of Sanders quasi-polynomial Freiman-Ruzsa theorem

RSS-Feed




TR12-029
Authors: Shachar Lovett
Publication: 4th April 2012 00:06
Downloads: 1142
Keywords: 


Abstract:

The polynomial Freiman-Ruzsa conjecture is one of the important conjectures in additive combinatorics. It asserts than one can switch between combinatorial and algebraic notions of approximate subgroups with only a polynomial loss in the underlying parameters. This conjecture has also already found several applications in theoretical computer science. Recently, Tom Sanders proved a weaker version of the conjecture, with a quasi-polynomial loss in parameters. The aim of this note is to make his proof accessible to the theoretical computer science community, and in particular to people who are less familiar with additive combinatorics.



ISSN 1433-8092 | Imprint