The Quasi-Polynomial Freiman-Ruzsa Theorem of Sanders
| Computer Science/Discrete Mathematics Seminar II | |
| Topic: | The Quasi-Polynomial Freiman-Ruzsa Theorem of Sanders |
| Speaker: | Shachar Lovett |
| Affiliation: | Member, School of Mathematics |
| Date: | Tuesday, March 20 |
| Time/Room: | 10:30am - 12:30pm/S-101 |
The polynomial Freiman-Ruzsa conjecture is one of the important open problems in additive combinatorics. In computer science, it already has several diverse applications: explicit constructions of two-source extractors; improved bounds for the log rank conjecture in communication complexity; and lower bounds for locally decodable codes based on matching vectors codes. Recently, Tom Sanders proved a quasi-polynomial version of this conjecture. I will describe the polynomial Freiman-Ruzsa conjecture, its applications and the proof of Sanders theorem.