<p>The log-rank conjecture is equivalent to the following conjecture.</p>

<blockquote>
  <p>For any graph $G$ with adjacency matrix $A$ and complement graph $\bar{G}$, the chromatic number of $\bar{G}$ is at most $(\log \mathsf{rank}(A))^{O(1)}$. </p>
</blockquote>

<p>This is from Lovasz and Saks's original <a href="http://dl.acm.org/citation.cfm?id=1398604" rel="nofollow">paper</a>, which has more connections.</p>

<p><a href="http://rd.springer.com/article/10.1007%2FBF01192527" rel="nofollow">Nisan and Wigderson</a> observed that to prove the log-rank conjecture it suffices to show that any $M \in \{0, 1\}^{N \times N}$ has a monochromatic rectangle of size at least $N 2^{-(\log \mathsf{rank} M)^{O(1)}}$. </p>

<p>More intuitively, the hardness in trying to disprove the conjecture comes from the fact that it's difficult to construct a non-trivial example of a binary matrix that has low rank over the reals. The trivial examples are matrices that can be decomposed into a small number of combinatorial rectangles, but we know that such a decomposition implies small communication complexity. So the conjecture asks, are all low rank binary matrices decomposable into a small number of rectangles. </p>

CC BY-SA 3.0
2013-05-23T18:55:40.627Z
2013-05-23T21:47:43.727Z
2013-05-23T21:47:43.727Z
Sasho Nikolov
<p>Log rank conjecture is one of the most famous open problems in the area of communication compleixty. </p>

<p>Lets consider the two party cdommunication complexity. Alice and Bob have $n$ bit strings $a,b$ , respectively, and they wish to compute arbitrary boolean function $f(a,b)$.</p>

<p>Communication matrix of $f$ is a $2^{n}\times 2^{n}$ matrix whose indices  of row (column) corresponds to the inputs of Alice (Bob) and each entry $M_f (a,b)$ correspond to function value $f(a,b)$.</p>

<p>Log rank conjecture asserts that $CC(f) = (\log rank (M_{f}))^{O(1)}$  </p>

<p>On the other hand, rank is a crucial role in the linea algebra and similar concepts of rank are considered. </p>

<blockquote>
  <p>QUESTION:I am looking for similar conjectures in the area of communication compleixty and related compleixty theoretic areas, similar-seeming conjectures without the communication complexity machinery, similar-seeming conjectures in linear algebra.Is there an appropriate reference ?</p>
</blockquote>

CC BY-SA 3.0
2013-05-23T09:25:19.043Z
I don't understand what you are asking.  You have stated the log rank conjecture.  Are you looking for consequences, for similar conjectures in related areas, similar-seeming conjectures without the communication complexity machinery, or something else?
András Salamon
CC BY-SA 3.0
2013-05-23T19:48:48.450Z
Matrix rigidity asks about the least amount of perturbation required to substantially lower the rank of a matrix. Maybe that'd interest you.
Mahdi Cheraghchi
<cc.complexity-theory><co.combinatorics><linear-algebra><communication-complexity>
Various conjectures which is similar to Log Rank conjecture
echuly
# Various conjectures which is similar to Log Rank conjecture

(Asked by: username_0 on 2013-05-23)

Log rank conjecture is one of the most famous open problems in the area of communication compleixty.

Lets consider the two party cdommunication complexity. Alice and Bob have $n$ bit strings $a,b$ , respectively, and they wish to compute arbitrary boolean function $f(a,b)$.

Communication matrix of $f$ is a $2^{n}\times 2^{n}$ matrix whose indices of row (column) corresponds to the inputs of Alice (Bob) and each entry $M\_f (a,b)$ correspond to function value $f(a,b)$.

Log rank conjecture asserts that $CC(f) = (\log rank (M\_{f}))^{O(1)}$

On the other hand, rank is a crucial role in the linea algebra and similar concepts of rank are considered.

> QUESTION:I am looking for similar conjectures in the area of communication compleixty and related compleixty theoretic areas, similar-seeming conjectures without the communication complexity machinery, similar-seeming conjectures in linear algebra.Is there an appropriate reference ?

**Tags:** cc.complexity-theory, co.combinatorics, linear-algebra, communication-complexity

> **Comments:**
> **username_1**: I don't understand what you are asking.  You have stated the log rank conjecture.  Are you looking for consequences, for similar conjectures in related areas, similar-seeming conjectures without the communication complexity machinery, or something else?  
> **username_2**: Matrix rigidity asks about the least amount of perturbation required to substantially lower the rank of a matrix. Maybe that'd interest you.  

---

## 1 answers

### Answer by username_3 on 2013-05-23. Score: 3

The log-rank conjecture is equivalent to the following conjecture.

> For any graph $G$ with adjacency matrix $A$ and complement graph $\bar{G}$, the chromatic number of $\bar{G}$ is at most $(\log \mathsf{rank}(A))^{O(1)}$.

This is from Lovasz and Saks's original [paper](http://dl.acm.org/citation.cfm?id=1398604), which has more connections.

[Nisan and Wigderson](http://rd.springer.com/article/10.1007%2FBF01192527) observed that to prove the log-rank conjecture it suffices to show that any $M \in \{0, 1\}^{N \times N}$ has a monochromatic rectangle of size at least $N 2^{-(\log \mathsf{rank} M)^{O(1)}}$.

More intuitively, the hardness in trying to disprove the conjecture comes from the fact that it's difficult to construct a non-trivial example of a binary matrix that has low rank over the reals. The trivial examples are matrices that can be decomposed into a small number of combinatorial rectangles, but we know that such a decomposition implies small communication complexity. So the conjecture asks, are all low rank binary matrices decomposable into a small number of rectangles.


---

