{"77691":{"#nid":"77691","#data":{"type":"event","title":"ARC Colloquium: Eli Ben-Sasson, Technion - Israel Institute of Technology","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EFor a {0,1}-valued matrix M let CC(M) denote the deterministic communication complexity of the boolean function associated with M. The log-rank conjecture of Lovasz and Saks [FOCS 1988] states that CC(M) \u0026lt;= log^c(rank(M)) for some absolute constant c where rank(M) denotes the rank of M over the field of real numbers.\u003C\/p\u003E\u003Cp\u003EWe show that CC(M) \u0026lt;= c rank(M)\/ log rank(M) for some absolute constant c, assuming a well-known conjecture from additive combinatorics, known as the Polynomial Freiman-Ruzsa (PFR) conjecture.\u003C\/p\u003E\u003Cp\u003EOur proof is based on the study of the \u0022approximate duality conjecture\u0022 which was recently suggested by Ben-Sasson and Zewi [STOC 2011], and studied there in connection to the PFR conjecture. First we improve the bounds on approximate duality assuming the PFR conjecture. Then we use the approximate duality conjecture (with improved bounds) to get the aforementioned upper bound on the communication complexity of low-rank martices, and this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995]. \u003C\/p\u003E\u003Cp\u003EJoint work with Shachar Lovett and Noga Zewi\u003C\/p\u003E","summary":null,"format":"limited_html"}],"field_subtitle":"","field_summary":"","field_summary_sentence":[{"value":"An Additive Combinatorics Approach to the Study of the Log-rank Conjecture in Communication Complexity"}],"uid":"27263","created_gmt":"2012-01-11 16:46:13","changed_gmt":"2016-10-08 01:57:02","author":"Elizabeth Ndongi","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2012-03-12T14:00:00-04:00","event_time_end":"2012-03-12T14:00:00-04:00","event_time_end_last":"2012-03-12T14:00:00-04:00","gmt_time_start":"2012-03-12 18:00:00","gmt_time_end":"2012-03-12 18:00:00","gmt_time_end_last":"2012-03-12 18:00:00","rrule":null,"timezone":"America\/New_York"},"extras":[],"groups":[{"id":"50875","name":"School of Computer Science"},{"id":"70263","name":"ARC"}],"categories":[],"keywords":[],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1795","name":"Seminar\/Lecture\/Colloquium"}],"invited_audience":[],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[{"value":"\u003Cp\u003E\u003Ca href=\u0022mailto:ndongi@cc.gatech.edu\u0022\u003Endongi@cc.gatech.edu\u003C\/a\u003E\u003C\/p\u003E","format":"limited_html"}],"email":[],"slides":[],"orientation":[],"userdata":""}}}