Skip to main navigation
Skip to Content
Computer Science
University of Toronto
U of T Portal
Student Support
Contact
About
History of U of T Computer Science
Computer Science at U of T Mississauga
Computer Science at U of T Scarborough
Employment Opportunities for Faculty/Lecturers
How to Find Us
Contact
Undergraduate
Prospective Undergraduates
Current Undergraduates
Graduate
Prospective Graduate Students
Current Graduate Students
Research
Research Areas
Partner with us
People
Faculty
Staff
In Memoriam
Alumni and Friends
Honours & Awards
Women in Computer Science
Graduate Student Society
Undergraduate Student Union
Undergraduate Artificial Intelligence Group
Undergraduate Theory Group
News & Events
News
Events
@DCS Update
Alumni
Donate
You are viewing: >
Home
>
News & Events
>
Events
> Theory Seminar- Feb 5
About
Undergraduate
Graduate
Research
People
News & Events
Theory Seminar- Feb 5
Event date: Wednesday, February 05, 2014, at 11:10 AM
Location: GB221
Speaker: Noga Ron-Zewi, Technion, Israel
Title: The polynomial Freiman-Ruzsa conjecture in additive combinatorics and its applications in computational complexity
Abstract:
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 attemptsto 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.