Computer Science/Discrete Mathematics Seminar II

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.