Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-008 | 17th January 2024 12:07

Hard submatrices for non-negative rank and communication complexity }

RSS-Feed




TR24-008
Authors: Pavel Hrubes
Publication: 17th January 2024 22:30
Downloads: 208
Keywords: 


Abstract:

Given a non-negative real matrix $M$ of non-negative rank at least $r$, can we witness this fact by a small submatrix of $M$? While Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: an $m\times n$ matrix always contains a submatrix with at most $r^3$ rows and columns of non-negative rank at least $\Omega(\frac{r}{\log n\log m})$. A similar result is proved for the $1$-partition number of a Boolean matrix and, consequently, also for its two-player deterministic communication complexity. Tightness of the latter estimate is closely related to Log-rank conjecture.



ISSN 1433-8092 | Imprint