Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > APPROXIMATE DUALITY:
Reports tagged with approximate duality:
TR11-157 | 25th November 2011
Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi

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

Revisions: 1

For 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$) is at most $\log^c({\mbox{rank}}(M))$ for some absolute constant $c$ where rank($M$) denotes the rank of $M$ over the field ... more >>>




ISSN 1433-8092 | Imprint