ECCC-Report TR24-008https://eccc.weizmann.ac.il/report/2024/008Comments and Revisions published for TR24-008en-usWed, 15 May 2024 17:13:25 +0300
Revision 1
| Hard submatrices for non-negative rank and communication complexity |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2024/008#revision1Given 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.
Wed, 15 May 2024 17:13:25 +0300https://eccc.weizmann.ac.il/report/2024/008#revision1
Paper TR24-008
| Hard submatrices for non-negative rank and communication complexity } |
Pavel Hrubes
https://eccc.weizmann.ac.il/report/2024/008Given 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.
Wed, 17 Jan 2024 22:30:18 +0200https://eccc.weizmann.ac.il/report/2024/008