Theory of Computing Library
Graduate Surveys 6
Graduate Surveys 6
An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem
Published: July 29, 2015 (14 pages)
Keywords: additive combinatorics, Fourier analysis
ACM Classification: F.2.2
AMS Classification: 68Q17, 68Q25
Abstract: [Plain Text Version]
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.
Licensed under a Creative Commons Attribution License (CC-BY)