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

Computer Science – Computational Complexity

Scientific paper

Rate now

  [ 0.00 ] – not rated yet Voters 0   Comments 0

Details

Scientific paper

For a $\{0,1\}$-valued matrix $M$ let $\rm{CC}(M)$ denote the deterministic communication complexity of the boolean function associated with $M$. The log-rank conjecture of Lov\'{a}sz and Saks [FOCS 1988] states that $\rm{CC}(M) \leq \log^c(\rm{rank}(M))$ for some absolute constant $c$ where $\rm{rank}(M)$ denotes the rank of $M$ over the field of real numbers. We show that $\rm{CC}(M)\leq c \cdot \rm{rank}(M)/\log \rm{rank}(M)$ for some absolute constant $c$, assuming a well-known conjecture from additive combinatorics known as the Polynomial Freiman-Ruzsa (PFR) conjecture. Our proof is based on the study of the "approximate duality conjecture" 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, where this part uses the methodology suggested by Nisan and Wigderson [Combinatorica 1995].

No associations

LandOfFree

Say what you really think

Search LandOfFree.com for scientists and scientific papers. Rate them and share your experience with other people.

Rating

An additive combinatorics approach to the log-rank conjecture in communication complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with An additive combinatorics approach to the log-rank conjecture in communication complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An additive combinatorics approach to the log-rank conjecture in communication complexity will most certainly appreciate the feedback.

Rate now

     

Profile ID: LFWR-SCP-O-173451

  Search
All data on this website is collected from public sources. Our data reflects the most accurate information available at the time of publication.