# Computer Science/Discrete Mathematics Seminar I

## Marton's Conjecture, aka the Polynomial Freiman--Ruzsa conjecture

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.

### Date & Time

January 22, 2024 | 11:00am – 12:00pm

### Location

Simonyi 101 and Remote Access### Speakers

Frederick Manners, University of California San Diego