Under the auspices of the Computational Complexity Foundation (CCF)

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