# Various conjectures which is similar to Log Rank conjecture

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 ?

• 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? May 23, 2013 at 9:25
• Matrix rigidity asks about the least amount of perturbation required to substantially lower the rank of a matrix. Maybe that'd interest you. May 23, 2013 at 19:48

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)}$.
Nisan and Wigderson 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)}}$.