{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,13]],"date-time":"2026-05-13T19:26:12Z","timestamp":1778700372022,"version":"3.51.4"},"reference-count":17,"publisher":"Springer Science and Business Media LLC","issue":"1-2","license":[{"start":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T00:00:00Z","timestamp":1720137600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T00:00:00Z","timestamp":1720137600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001711","name":"Schweizerischer Nationalfonds zur F\u00f6rderung der Wissenschaftlichen Forschung","doi-asserted-by":"publisher","award":["200021-196965"],"award-info":[{"award-number":["200021-196965"]}],"id":[{"id":"10.13039\/501100001711","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2025,7]]},"abstract":"Abstract<\/jats:title>\n Given an \n \n $$m\\times n$$<\/jats:tex-math>\n \n \n m<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> binary matrix M<\/jats:italic> with \n \n $$|M|=p\\cdot mn$$<\/jats:tex-math>\n \n \n |<\/mml:mo>\n M<\/mml:mi>\n |<\/mml:mo>\n =<\/mml:mo>\n p<\/mml:mi>\n \u00b7<\/mml:mo>\n m<\/mml:mi>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> (where |M<\/jats:italic>| denotes the number of 1 entries), define the discrepancy<\/jats:italic> of M<\/jats:italic> as \n \n $${{\\,\\textrm{disc}\\,}}(M)=\\displaystyle \\max \\nolimits _{X\\subset [m], Y\\subset [n]}\\big ||M[X\\times Y]|-p|X|\\cdot |Y|\\big |$$<\/jats:tex-math>\n \n \n \n \n \n disc<\/mml:mtext>\n \n <\/mml:mrow>\n \n (<\/mml:mo>\n M<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n =<\/mml:mo>\n \n max<\/mml:mo>\n \n X<\/mml:mi>\n \u2282<\/mml:mo>\n [<\/mml:mo>\n m<\/mml:mi>\n ]<\/mml:mo>\n ,<\/mml:mo>\n Y<\/mml:mi>\n \u2282<\/mml:mo>\n [<\/mml:mo>\n n<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msub>\n \n \n |<\/mml:mo>\n <\/mml:mrow>\n |<\/mml:mo>\n M<\/mml:mi>\n \n [<\/mml:mo>\n X<\/mml:mi>\n \u00d7<\/mml:mo>\n Y<\/mml:mi>\n ]<\/mml:mo>\n <\/mml:mrow>\n |<\/mml:mo>\n <\/mml:mrow>\n -<\/mml:mo>\n \n p<\/mml:mi>\n |<\/mml:mo>\n X<\/mml:mi>\n |<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n \n |<\/mml:mo>\n Y<\/mml:mi>\n |<\/mml:mo>\n \n |<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:mstyle>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>. Using semidefinite programming and spectral techniques, we prove that if \n \n $${{\\,\\textrm{rank}\\,}}(M)\\le r$$<\/jats:tex-math>\n \n \n \n \n rank<\/mml:mtext>\n \n <\/mml:mrow>\n (<\/mml:mo>\n M<\/mml:mi>\n )<\/mml:mo>\n \u2264<\/mml:mo>\n r<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> and \n \n $$p\\le 1\/2$$<\/jats:tex-math>\n \n \n p<\/mml:mi>\n \u2264<\/mml:mo>\n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>, then \n \n $$\\begin{aligned}{{\\,\\textrm{disc}\\,}}(M)\\ge \\Omega (mn)\\cdot \\min \\left\\{ p,\\frac{p^{1\/2}}{\\sqrt{r}}\\right\\} .\\end{aligned}$$<\/jats:tex-math>\n \n \n \n \n \n \n \n \n disc<\/mml:mtext>\n \n <\/mml:mrow>\n \n (<\/mml:mo>\n M<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u2265<\/mml:mo>\n \u03a9<\/mml:mi>\n \n (<\/mml:mo>\n m<\/mml:mi>\n n<\/mml:mi>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00b7<\/mml:mo>\n min<\/mml:mo>\n \n p<\/mml:mi>\n ,<\/mml:mo>\n \n \n p<\/mml:mi>\n \n 1<\/mml:mn>\n \/<\/mml:mo>\n 2<\/mml:mn>\n <\/mml:mrow>\n <\/mml:msup>\n \n r<\/mml:mi>\n <\/mml:msqrt>\n <\/mml:mfrac>\n <\/mml:mfenced>\n .<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mtd>\n <\/mml:mtr>\n <\/mml:mtable>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:disp-formula>We use this result to obtain a modest improvement of Lovett\u2019s best known upper bound on the log-rank conjecture. We prove that any \n \n $$m\\times n$$<\/jats:tex-math>\n \n \n m<\/mml:mi>\n \u00d7<\/mml:mo>\n n<\/mml:mi>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> binary matrix M<\/jats:italic> of rank at most r<\/jats:italic> contains an \n \n $$(m\\cdot 2^{-O(\\sqrt{r})})\\times (n\\cdot 2^{-O(\\sqrt{r})})$$<\/jats:tex-math>\n \n \n \n (<\/mml:mo>\n m<\/mml:mi>\n \u00b7<\/mml:mo>\n \n 2<\/mml:mn>\n \n -<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n \n r<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n \u00d7<\/mml:mo>\n \n (<\/mml:mo>\n n<\/mml:mi>\n \u00b7<\/mml:mo>\n \n 2<\/mml:mn>\n \n -<\/mml:mo>\n O<\/mml:mi>\n (<\/mml:mo>\n \n r<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:msup>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula> sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank r<\/jats:italic> is at most \n \n $$O(\\sqrt{r})$$<\/jats:tex-math>\n \n \n O<\/mml:mi>\n (<\/mml:mo>\n \n r<\/mml:mi>\n <\/mml:msqrt>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:math>\n <\/jats:alternatives>\n <\/jats:inline-formula>.\n<\/jats:p>","DOI":"10.1007\/s10107-024-02117-9","type":"journal-article","created":{"date-parts":[[2024,7,5]],"date-time":"2024-07-05T10:01:36Z","timestamp":1720173696000},"page":"567-579","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Matrix discrepancy and the log-rank conjecture"],"prefix":"10.1007","volume":"212","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3307-9475","authenticated-orcid":false,"given":"Benny","family":"Sudakov","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Istv\u00e1n","family":"Tomon","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2024,7,5]]},"reference":[{"issue":"4","key":"2117_CR1","doi-asserted-by":"publisher","first-page":"787","DOI":"10.1137\/S0097539704441629","volume":"35","author":"N Alon","year":"2006","unstructured":"Alon, N., Naor, A.: Approximating the cut-norm via Grothendieck\u2019s inequality. SIAM J. Comput. 35(4), 787\u2013803 (2006)","journal-title":"SIAM J. Comput."},{"key":"2117_CR2","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1002\/jgt.3190120113","volume":"12","author":"P Erd\u0151s","year":"1988","unstructured":"Erd\u0151s, P., Goldberg, M., Pach, J., Spencer, J.: Cutting a graph into two dissimilar halves. J. Graph Theory 12, 121\u2013131 (1988)","journal-title":"J. Graph Theory"},{"key":"2117_CR3","unstructured":"Gavinsky, D., Lovett, S.: En route to the log-rank conjecture: New reductions and equivalent formulations. Electronic Colloquium on Computational Complexity (ECCC\u201913) (2013) 20, 80"},{"issue":"6","key":"2117_CR4","doi-asserted-by":"publisher","first-page":"2435","DOI":"10.1137\/16M1059369","volume":"47","author":"M G\u00f6\u00f6s","year":"2018","unstructured":"G\u00f6\u00f6s, M., Pitassi, T., Watson, T.: Deterministic communication versus partition number. SIAM J. Comput. 47(6), 2435\u20132450 (2018)","journal-title":"SIAM J. Comput."},{"key":"2117_CR5","first-page":"1","volume":"8","author":"A Grothendieck","year":"1953","unstructured":"Grothendieck, A.: R\u00e9sum\u00e9 de la th\u00e9orie m\u00e9trique des produits tensoriels topologiques. Bol. Soc. Mat. Sao Paulo 8, 1\u201379 (1953)","journal-title":"Bol. Soc. Mat. Sao Paulo"},{"key":"2117_CR6","unstructured":"John, F.: Extremum problems with inequalities as subsidiary conditions. In Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948, pages 187\u2013204. Interscience Publishers, Inc., New York, N. Y., (1948)"},{"key":"2117_CR7","volume-title":"Communication complexity","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E., Nisan, N.: Communication complexity. Cambridge University Press, New York, NY (1997)"},{"key":"2117_CR8","doi-asserted-by":"publisher","first-page":"441","DOI":"10.1007\/s11856-023-2517-5","volume":"256","author":"T Lee","year":"2023","unstructured":"Lee, T., Shraibman, A.: Around the log-rank conjecture. Israel J. Math. 256, 441\u2013477 (2023)","journal-title":"Israel J. Math."},{"issue":"4","key":"2117_CR9","doi-asserted-by":"publisher","first-page":"439","DOI":"10.1007\/s00493-007-2160-5","volume":"27","author":"N Linial","year":"2007","unstructured":"Linial, N., Mendelson, S., Schechtman, G., Shraibman, A.: Complexity measures of sign matrices. Combinatorica 27(4), 439\u2013463 (2007)","journal-title":"Combinatorica"},{"issue":"1\u20132","key":"2117_CR10","doi-asserted-by":"publisher","first-page":"227","DOI":"10.1017\/S0963548308009656","volume":"18","author":"N Linial","year":"2009","unstructured":"Linial, N., Shraibman, A.: Learning complexity versus communication complexity. Comb. Probab. Comput. 18(1\u20132), 227\u2013245 (2009)","journal-title":"Comb. Probab. Comput."},{"key":"2117_CR11","volume-title":"Combinatorial Problems and Exercises","author":"L Lov\u00e1sz","year":"2007","unstructured":"Lov\u00e1sz, L.: Combinatorial Problems and Exercises, 2nd Ed. AMS Chelsea Publishing (2007)","edition":"2nd Ed."},{"key":"2117_CR12","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Saks, M.: Lattices, M\u00f6bius functions and communication complexity. Annual Symposium on Foundations of Computer Science, 81\u201390 (1988)","DOI":"10.1109\/SFCS.1988.21924"},{"issue":"1","key":"2117_CR13","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/2724704","volume":"63","author":"S Lovett","year":"2016","unstructured":"Lovett, S.: Communication is bounded by root of rank. J. ACM 63(1), 1:1-1:9 (2016)","journal-title":"J. ACM"},{"key":"2117_CR14","unstructured":"Milojevi\u0107, A., Sudakov, B., Tomon, I.: Point-hyperplane incidences via extremal graph theory. preprint, arxiv:2401.06670 (2024)"},{"key":"2117_CR15","doi-asserted-by":"crossref","unstructured":"Nisan, N., Wigderson, A.: On rank vs. communication complexity. Proceedings of the 35rd Annual Symposium on Foundations of Computer Science 831\u2013836, (1994)","DOI":"10.1109\/SFCS.1994.365711"},{"key":"2117_CR16","unstructured":"R\u00e4ty, E., Sudakov, B., Tomon, I.: Positive discrepancy, MaxCut, and eigenvalues of graphs. preprint, arxiv:2311.02070 (2023)"},{"issue":"2","key":"2117_CR17","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/3543684","volume":"14","author":"N Singer","year":"2022","unstructured":"Singer, N., Sudan, M.: Point-hyperplane incidence geometry and the log-rank conjecture. ACM Trans. Comput. Theory (TOCT) 14(2), 1\u201316 (2022)","journal-title":"ACM Trans. Comput. Theory (TOCT)"}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02117-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-024-02117-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-024-02117-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:02:47Z","timestamp":1750176167000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-024-02117-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,7,5]]},"references-count":17,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2025,7]]}},"alternative-id":["2117"],"URL":"https:\/\/doi.org\/10.1007\/s10107-024-02117-9","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"value":"0025-5610","type":"print"},{"value":"1436-4646","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,7,5]]},"assertion":[{"value":"11 February 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 June 2024","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 July 2024","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}