2026-07-23T16:56:26Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:20409 2024-07-15T12:26:45Z ddc:004 open_access

Hard Submatrices for Non-Negative Rank and Communication Complexity Hrubeš, Pavel Non-negative rank communication complexity extension complexity 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×n matrix of non-negative rank r always contains a submatrix with at most r³ rows and columns with non-negative rank at least Ω(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 the log-rank conjecture of Lovász and Saks. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pavel Hrubeš 2024 Is Part Of LIPIcs, Volume 300, 39th Computational Complexity Conference (CCC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CCC.2024.13 urn:nbn:de:0030-drops-204097 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2024.13 eng https://creativecommons.org/licenses/by/4.0/legalcode