{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:05:08Z","timestamp":1764781508673,"version":"3.46.0"},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T00:00:00Z","timestamp":1755043200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T00:00:00Z","timestamp":1755043200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["comput. complex."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Given a non-negative real matrix\n                    <jats:italic>M<\/jats:italic>\n                    of non-negative rank at least\n                    <jats:italic>r<\/jats:italic>\n                    , can we witness this fact by a small submatrix of\n                    <jats:italic>M<\/jats:italic>\n                    ? While  Moitra (SIAM J. Comput. 2013) proved that this cannot be achieved exactly, we show that such a witnessing is possible approximately: An\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$m\\times n$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>m<\/mml:mi>\n                            <mml:mo>\u00d7<\/mml:mo>\n                            <mml:mi>n<\/mml:mi>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    matrix of non-negative rank\n                    <jats:italic>r<\/jats:italic>\n                    always contains a submatrix with at most\n                    <jats:italic>r<\/jats:italic>\n                    <jats:sup>3<\/jats:sup>\n                    rows and columns with non-negative rank at least\n                    <jats:inline-formula>\n                      <jats:alternatives>\n                        <jats:tex-math>$$\\Omega(\\frac{r}{\\log n\\log m})$$<\/jats:tex-math>\n                        <mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                          <mml:mrow>\n                            <mml:mi>\u03a9<\/mml:mi>\n                            <mml:mo>(<\/mml:mo>\n                            <mml:mfrac>\n                              <mml:mi>r<\/mml:mi>\n                              <mml:mrow>\n                                <mml:mo>log<\/mml:mo>\n                                <mml:mi>n<\/mml:mi>\n                                <mml:mo>log<\/mml:mo>\n                                <mml:mi>m<\/mml:mi>\n                              <\/mml:mrow>\n                            <\/mml:mfrac>\n                            <mml:mo>)<\/mml:mo>\n                          <\/mml:mrow>\n                        <\/mml:math>\n                      <\/jats:alternatives>\n                    <\/jats:inline-formula>\n                    . 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\u00e1sz and Saks.\n                  <\/jats:p>","DOI":"10.1007\/s00037-025-00269-4","type":"journal-article","created":{"date-parts":[[2025,8,13]],"date-time":"2025-08-13T12:54:59Z","timestamp":1755089699000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Hard submatrices for non-negative rank and communication complexity"],"prefix":"10.1007","volume":"34","author":[{"given":"Pavel","family":"Hrube\u0161","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2025,8,13]]},"reference":[{"doi-asserted-by":"crossref","unstructured":"S. Basu, R. Pollack & M.F. Roy (2006). Algorithms in real algebraic geometry. Springer-Verlag.","key":"269_CR1","DOI":"10.1007\/3-540-33099-2"},{"doi-asserted-by":"crossref","unstructured":"G. Braun, S. Fiorini, S. Pokutta & D. Steuer (2015). Approximation Limits of Linear Programs (Beyond Hierarchies). Math. of Operations Research 40(3), 756-772.","key":"269_CR2","DOI":"10.1287\/moor.2014.0694"},{"unstructured":"S. Chandran, D. Issac & A. Karrenbauer (2016). On the Parameterized Complexity of Biclique Cover and Partition. In International Symposium on Parameterized and Exact Computation. 11(3), 1-11.","key":"269_CR3"},{"doi-asserted-by":"crossref","unstructured":"P. Erd\u00f6s (1988). Problems and Results in Combinatorial Analysis and Graph Theory. Annals of Discrete Mathematics 38, 81-92.","key":"269_CR4","DOI":"10.1016\/S0167-5060(08)70773-8"},{"doi-asserted-by":"crossref","unstructured":"S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary & R. de Wolf (2011). Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds. In STOC '12: Proceedings of the forty-fourth annual ACM symposium on Theory of computing, 95-106.","key":"269_CR5","DOI":"10.1145\/2213977.2213988"},{"doi-asserted-by":"crossref","unstructured":"M. G\u00f6\u00f6s, I. Newman, A. Riazanov & D. Sokolov (2024). ardness Condensation by Restriction. STOC 2024: Proceedings of the 56th Annual ACM Symposium on Theory of Computing, 2016-2027.","key":"269_CR6","DOI":"10.1145\/3618260.3649711"},{"doi-asserted-by":"crossref","unstructured":"P. Hrube\u0161 (2020a). On $$\\epsilon$$-sensitive monotone computations. Computational Complexity 29(2), 6.","key":"269_CR7","DOI":"10.1007\/s00037-020-00196-6"},{"unstructured":"P. Hrube\u0161 (2020b). On the complexity of computing a random Boolean function over the reals. Theory of Computing 16(9), 1-12.","key":"269_CR8"},{"doi-asserted-by":"crossref","unstructured":"P. Hrube\u0161 & N. Talebanfard (2022). On the Extension Complexity of Polytopes Separating Subsets of the Boolean Cube. Disc. and Comp. Geom. 70(1), 268-278.","key":"269_CR9","DOI":"10.1007\/s00454-022-00419-3"},{"doi-asserted-by":"crossref","unstructured":"R. Impagliazzo (1995). Hard-core distributions for somewhat hard problems. In Proceedings of IEEE 36th Annual Foundations of Computer Science, 538-545.","key":"269_CR10","DOI":"10.1109\/SFCS.1995.492584"},{"doi-asserted-by":"crossref","unstructured":"E. Kushilevitz & N. Nisan (1996). Communication Complexity. Cambridge University Press.","key":"269_CR11","DOI":"10.1017\/CBO9780511574948"},{"doi-asserted-by":"crossref","unstructured":"M. Kwan, L. Sauermann & Y. Zhao (2022). Extension complexity of low-dimensional polytopes. Transactions of the American Mathematical Society 375(6), 4209-4250.","key":"269_CR12","DOI":"10.1090\/tran\/8614"},{"doi-asserted-by":"crossref","unstructured":"R. Lipton & N. Young (1994). Simple strategies for large zero-sum games with applications to complexity theory. STOC '94: Proceedings of the twenty-sixth annual ACM symposium on Theory of Computing, 734-740.","key":"269_CR13","DOI":"10.1145\/195058.195447"},{"doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz & M. Saks (1988). Lattices, mobius functions and communications complexity. In 29th Annual Symposium on Foundations of Computer Science (FOCS 1988), 81-90.","key":"269_CR14","DOI":"10.1109\/SFCS.1988.21924"},{"doi-asserted-by":"crossref","unstructured":"A. Moitra (2016). An almost optimal algorithm for computing nonnegative rank. In SIAM J. Comput. 45(1), 156-173.","key":"269_CR15","DOI":"10.1137\/140990139"},{"doi-asserted-by":"crossref","unstructured":"A. Rao & A. Yehudayoff (2020). Communication Complexity and Applications. Cambridge University Press.","key":"269_CR16","DOI":"10.1017\/9781108671644"},{"doi-asserted-by":"crossref","unstructured":"V. R\u00f6dl & R. A. Duke (1985). On graphs with small subgraphs of large chromatic number. Graphs and Combinatorics 1, 91-96.","key":"269_CR17","DOI":"10.1007\/BF02582932"},{"doi-asserted-by":"crossref","unstructured":"T. Rothvoss (2013). Some 0\/1 polytopes need exponential size extended formulations. Math. Program. 142, 255-268.","key":"269_CR18","DOI":"10.1007\/s10107-012-0574-3"},{"unstructured":"Y. Shitov (2014). Sublinear extension of polygons. arXiv:1412.0728.","key":"269_CR19"},{"doi-asserted-by":"crossref","unstructured":"M. Yannakakis (1991). Expressing combinatorial optimization problems by linear programs. Journal of Computer and System Sciences 43(3), 441-466.","key":"269_CR20","DOI":"10.1016\/0022-0000(91)90024-Y"}],"container-title":["computational complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00269-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00037-025-00269-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00037-025-00269-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,3]],"date-time":"2025-12-03T17:00:12Z","timestamp":1764781212000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00037-025-00269-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,8,13]]},"references-count":20,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["269"],"URL":"https:\/\/doi.org\/10.1007\/s00037-025-00269-4","relation":{},"ISSN":["1016-3328","1420-8954"],"issn-type":[{"type":"print","value":"1016-3328"},{"type":"electronic","value":"1420-8954"}],"subject":[],"published":{"date-parts":[[2025,8,13]]},"assertion":[{"value":"27 September 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 August 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"9"}}