Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

The polynomial Freiman-Ruzsa conjecture in additive combinatorics and its applications in computational complexity
event speaker icon
Noga Zewi (Ph.D. Thesis Seminar)
event date icon
Wednesday, 07.05.2014, 14:30
event location icon
Taub 601
event speaker icon
Advisor: Prof. Eli Ben-Sasson
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.