Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LOG-RANK CONJECTURE:
Reports tagged with Log-rank conjecture:
TR11-025 | 19th February 2011
Yang Li

#### Monotone Rank and Separations in Computational Complexity

In the paper, we introduce the concept of monotone rank, and using it as a powerful tool, we obtain several important and strong separation results in computational complexity.

\begin{itemize}

\item We show a super-exponential separation between monotone and non-monotone computation in the non-commutative model, and thus give the answer to ... more >>>

TR13-084 | 8th June 2013
Shachar Lovett

#### Communication is bounded by root of rank

Revisions: 1

We prove that any total boolean function of rank $r$ can be computed by a deterministic communication protocol of complexity $O(\sqrt{r} \cdot \log(r))$. Equivalently, any graph whose adjacency matrix has rank $r$ has chromatic number at most $2^{O(\sqrt{r} \cdot \log(r))}$. This gives a nearly quadratic improvement in the dependence on ... more >>>

ISSN 1433-8092 | Imprint