Theory of Computing Library Graduate Surveys
---------------------------------------------------
Title : An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem
Authors : Shachar Lovett
Number : 6
Pages : 1-14
URL : http://www.theoryofcomputing.org/articles/gs006
Abstract
--------
The polynomial Freiman-Ruzsa conjecture is one of the most important
conjectures in additive combinatorics. It asserts that one can switch
between combinatorial and algebraic notions of approximate subgroups
with only a polynomial loss in the underlying parameters. This
conjecture has also 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 readers who are less familiar
with additive combinatorics.