Computer Science/Discrete Mathematics Seminar I

A function $f : \mathbb{F}_2^n \to \mathbb{F}_2^n$ is linear if $f(x+y)=f(x)+f(y)$ for all pairs $(x,y)$.

Suppose $f$ is "a bit linear" -- say, $f(x+y)=f(x)+f(y)$ for 1% of pairs $(x,y)$.  Must $f$ agree with a truly linear function a positive proportion of the time?  How large a proportion?

This question turns out to be equivalent to asking for good quantitative bounds in the Freiman--Ruzsa theorem, a foundational result in additive combinatorics.  Marton gave a formulation, equivalent to the statement above, which she conjectured should have polynomial bounds.  I will outline a recent proof of this conjecture.

Joint work with Timothy Gowers, Ben Green and Terence Tao.