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 >>>

TR20-155 | 18th October 2020
Alexander Knop, Shachar Lovett, Sam McGuire, Weiqiang Yuan

#### Log-rank and lifting for AND-functions

Revisions: 1

Let $f: \{0,1\}^n \to \{0, 1\}$ be a boolean function, and let $f_\land (x, y) = f(x \land y)$ denote the AND-function of $f$, where $x \land y$ denotes bit-wise AND. We study the deterministic communication complexity of $f_\land$ and show that, up to a $\log n$ factor, it is ... more >>>

ISSN 1433-8092 | Imprint