An additive combinatorics approach relating communication complexity to rank
Speaker: Eli Ben-Sasson, Technion and MIT
Date: Tuesday, December 11 2012
Time: 4:15PM to 5:15PM
Refreshments: 3:45PM
Location: 32-124 Stata Center
Host: Dana Moshkovitz, CSAIL, MIT
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: One of the outstanding questions in communication complexity is that of relating the rank of a {0,1}-valued matrix M to its communication complexity. Mehlhorn and Schmidt [STOC 1982] showed that
log^{O(1)} rank(M) < Comm. Complexity (M) < O(rank(M))
and these asymptotic bounds have not changed in the past 30 years (but for the constants hidden in the asymptotic notation). We show, assuming the Polynomial Freiman-Ruzsa (PFR) conjecture in additive combinatorics, and using tools from that field, that
Comm. Complexity(M) < O(rank(M)/ log rank(M)).
Our proof is based on the study of the "approximate duality conjecture" [Ben-Sasson and Zewi STOC 2011] which has other applications to the construction of bipartite Ramsey graphs and to locally decodable codes.
Joint work with Shachar Lovett (IAS) and Noga Ron-Zewi (Technion), which will appear in FOCS 2012.
See other events that are part of Theory Colloquium 2012/2013
See other events happening in December 2012
