0
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – András Salamon May 23 '13 at 9:25
  • $\begingroup$ Matrix rigidity asks about the least amount of perturbation required to substantially lower the rank of a matrix. Maybe that'd interest you. $\endgroup$ – MCH May 23 '13 at 19:48
3
$\begingroup$

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, which has more connections.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.