An additive combinatorics approach to the log-rank conjecture in\n communication complexity

2011/11/24 by Eli Ben‐Sasson, Shachar Lovett, Ben-Sasson, Eli +3
Mathematics · Engineering · Computer Science · #Limits and Structures in Graph Theory #graph theory and CDMA systems #Graph Labeling and Dimension Problems

paper · pdf · doi:10.48550/arxiv.1111.5884

Abstract

For a 0,1 -valued matrix M let rmCC(M) denote the deterministic\ncommunication complexity of the boolean function associated with M. The\nlog-rank conjecture of Lov 'asz and Saks [FOCS 1988] states that rmCC(M)\n\≤ \log^c( rmrank(M)) for some absolute constant c where rmrank(M)\ndenotes the rank of M over the field of real numbers. We show that\n rmCC(M)\≤ c \⋅ rmrank(M)/\log rmrank(M) for some absolute\nconstant c, assuming a well-known conjecture from additive combinatorics\nknown as the Polynomial Freiman-Ruzsa (PFR) conjecture.\n Our proof is based on the study of the "approximate duality conjecture" which\nwas recently suggested by Ben-Sasson and Zewi [STOC 2011] and studied there in\nconnection to the PFR conjecture. First we improve the bounds on approximate\nduality assuming the PFR conjecture. Then we use the approximate duality\nconjecture (with improved bounds) to get the aforementioned upper bound on the\ncommunication complexity of low-rank martices, where this part uses the\nmethodology suggested by Nisan and Wigderson [Combinatorica 1995].\n

Cited by

• Additive combinatorics with a view towards computer science and\n cryptography: An exposition

Related

• A Note on the LogRank Conjecture in Communication Complexity
• Towards Stronger Counterexamples to the Log-Approximate-Rank Conjecture
• A direct proof for Lovett's bound on the communication complexity of low rank matrices
• Matrix discrepancy and the log-rank conjecture
• Log-rank and lifting for AND-functions