Sampling-based proof of the quasipolynomial Bogolyubov-Ruzsa theorem and algorithmic applications

Computer Science/Discrete Mathematics Seminar II
Topic:Sampling-based proof of the quasipolynomial Bogolyubov-Ruzsa theorem and algorithmic applications
Speaker:Noga Ron-Zewi
Affiliation:Member, School of Mathematics
Date:Tuesday, October 14
Time/Room:10:30am - 12:30pm/West Bldg. Lect. Hall

The polynomial Bogolyubov-Ruzsa conjecture which aims to quantify the amount of additive structure in dense subsets of abelian groups is one of the central conjectures in additive combinatorics which has recently been shown to have various applications in theoretical computer science. In a recent breakthrough, Sanders managed to prove a slightly weaker quasipolynomial version of this conjecture. In the talk I will present a simple proof of Sanders' result which relies only on the Chernoff bound for sampling and avoids the need for Lp norm estimates used in Sanders' original proof and discuss some algorithmic applications of this proof. Joint work with Eli Ben-Sasson, Madhur Tulsiani and Julia Wolf.