Latest update

# Logrank allowed extremal $0/1$ matrices?

2018-02-05 22:36:54

Can we have a $0/1$ real rank $r=O(n^{c})$ size $n^k2^{n^{c'}}\times n^k2^{n^{c'}}$ matrix with all rows and columns distinct with maximum eigenvalue $\leq n^{k'}2^{n^{c'}-\sqrt n}$ for some $10$ or would this violate the logrank conjecture? Discrepancy seems to be bound above by $O\big(\frac1{n^\alpha2^{\sqrt n}}\big)$ at some $\alpha\in\Bbb R$ and $\sqrt n$ is $r^{1/2c}$ and so communication complexity of the matrix would be $\Omega(r^{1/2c})$.

If the logrank conjecture is true then how small can the allowed maximum eigenvalue of such a matrix be? What is the best construction we know?