<p>Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.</p>

CC BY-SA 3.0
2017-06-07T16:59:46.890Z
2017-06-07T16:59:46.890Z
Shachar Lovett
<p>What is known about log rank conjecture in special situations of $O(\log N)$ rank $0/1$ matrix of size $N\times N$? Is there at least a conditional result showing better than $O(\sqrt{\log N})$ bound?</p>

<matrices><communication-complexity>
Low rank Log rank conjecture
Turbo
# Low rank Log rank conjecture

(Asked by: username_0 on 2015-03-16)

What is known about log rank conjecture in special situations of $O(\log N)$ rank $0/1$ matrix of size $N\times N$? Is there at least a conditional result showing better than $O(\sqrt{\log N})$ bound?

**Tags:** matrices, communication-complexity

---

## 1 answers

### Answer by username_1 on 2017-06-07. Score: 6

Not that I am aware of. This is unknown even for special cases, e.g. XOR functions.


---

