The Taub Faculty of Computer Science Events and Talks

Additive combinatorics is the branch of mathematics whose objects of study are subsets of integers (or other mathematical groups), and which studies the properties and patterns in these subsets that can be expressed via the basic operations of addition or multiplication. One of the central conjectures in additive combinatorics is the polynomial Freiman-Ruzsa conjecture which attempts to classify approximate subgroups of abelian groups. In a recent breakthrough [Sanders, Anal. PDE 2012], a slightly weaker quasipolynomial version of this conjecture was proven. In the talk I will present various applications of the polynomial Freiman-Ruzsa conjecture in computational complexity: To the construction of two-source extractors [Ben-Sasson-R., STOC 2011], to relating rank to communication complexity [Ben-Sasson-Lovett-R., FOCS 2012] and to lower bounds on matching vector codes [Bhowick-Dvir-Lovett, STOC 2013]. All these applications are derived via the approximate duality conjecture which was introduced in [Ben-Sasson-R., STOC 2011] and was shown to have tight relations with the polynomial Freiman-Ruzsa conjecture.