{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T12:00:15Z","timestamp":1768910415140,"version":"3.49.0"},"reference-count":31,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,7,1]],"date-time":"2014-07-01T00:00:00Z","timestamp":1404172800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Israel Ministry of Science and Technology"},{"DOI":"10.13039\/100000121","name":"Division of Mathematical Sciences","doi-asserted-by":"publisher","award":["DMS-0835373"],"award-info":[{"award-number":["DMS-0835373"]}],"id":[{"id":"10.13039\/100000121","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004963","name":"Seventh Framework Programme","doi-asserted-by":"publisher","award":["240258, 257575"],"award-info":[{"award-number":["240258, 257575"]}],"id":[{"id":"10.13039\/501100004963","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1350481"],"award-info":[{"award-number":["1350481"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2014,7]]},"abstract":"<jats:p>\n            Identifying complexity measures that bound the communication complexity of a {0,1}-valued matrix\n            <jats:italic>M<\/jats:italic>\n            is one the most fundamental problems in communication complexity. Mehlhorn and Schmidt [1982] were the first to suggest matrix-rank as one such measure. Among other things, they showed log rank F(M) CC(M) rankF2(M), where\n            <jats:italic>CC<\/jats:italic>\n            (\n            <jats:italic>M<\/jats:italic>\n            ) denotes the (deterministic) communication complexity of the function associated with\n            <jats:italic>M<\/jats:italic>\n            , and the rank on the left-hand side is over any field\n            <jats:italic>F<\/jats:italic>\n            and on the right-hand side it is over the two-element field\n            <jats:italic>F<\/jats:italic>\n            2. For certain matrices\n            <jats:italic>M<\/jats:italic>\n            , communication complexity equals the right-hand side, and this completely settles the question of \u201ccommunication complexity vs.\n            <jats:italic>F<\/jats:italic>\n            2-rank\u201d.\n          <\/jats:p>\n          <jats:p>\n            Here we reopen this question by pointing out that, when\n            <jats:italic>M<\/jats:italic>\n            has an additional natural combinatorial property---high discrepancy with respect to distributions which are uniform over submatrices---then communication complexity can be sublinear in\n            <jats:italic>F<\/jats:italic>\n            2-rank. Assuming the Polynomial Freiman-Ruzsa (PFR) conjecture in additive combinatorics, we show that CC(M) O(rank F2(M)\/log rank F2(M)) for any matrix\n            <jats:italic>M<\/jats:italic>\n            which satisfies this combinatorial property.\n          <\/jats:p>\n          <jats:p>\n            We also observe that if\n            <jats:italic>M<\/jats:italic>\n            has low rank over the reals, then it has low rank over\n            <jats:italic>F<\/jats:italic>\n            2 and it additionally satisfies this combinatorial property. As a corollary, our results also give the first (conditional) sublinear bound on communication complexity in terms of rank over the reals, a result improved later by Lovett [2014].\n          <\/jats:p>\n          <jats:p>Our proof is based on the study of the \u201capproximate duality conjecture\u201d which was suggested by Ben-Sasson and Zewi [2011] and studied there in connection to the PFR conjecture. First, we improve the bounds on approximate duality assuming the PFR conjecture. Then, we use the approximate duality conjecture (with improved bounds) to get our upper bound on the communication complexity of low-rank matrices.<\/jats:p>","DOI":"10.1145\/2629598","type":"journal-article","created":{"date-parts":[[2014,8,12]],"date-time":"2014-08-12T13:53:48Z","timestamp":1407851628000},"page":"1-18","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["An Additive Combinatorics Approach Relating Rank to Communication Complexity"],"prefix":"10.1145","volume":"61","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[{"name":"Technion - Israel Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Shachar","family":"Lovett","sequence":"additional","affiliation":[{"name":"University of California, San Diego"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Noga","family":"Ron-Zewi","sequence":"additional","affiliation":[{"name":"Technion - Israel Institute of Technology"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01212974"},{"key":"e_1_2_1_3_1","unstructured":"Eli Ben-Sasson and Noga Ron-Zewi. 2012. From affine to two-source extractors via approximate duality. In Electronic Colloquium on Computational Complexity (ECCC). http:\/\/eccc.hpi-web.de\/report\/2010\/144\/ (Revision 1 (2012)).  Eli Ben-Sasson and Noga Ron-Zewi. 2012. From affine to two-source extractors via approximate duality. In Electronic Colloquium on Computational Complexity (ECCC) . http:\/\/eccc.hpi-web.de\/report\/2010\/144\/ (Revision 1 (2012))."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993661"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488713"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-010-0101-8"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548312000351"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(88)90199-9"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050065"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2380656.2380679"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1112\/S0024609305018102"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548309009821"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0305004110000186"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199709)26:1%3C1::AID-JGT1%3E3.0.CO;2-N"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-0118(199610)23:2%3C185::AID-JGT9%3E3.0.CO;2-P"},{"key":"e_1_2_1_17_1","volume-title":"Communication Complexity","author":"Kushilevitz Eyal","unstructured":"Eyal Kushilevitz and Noam Nisan . 1997. Communication Complexity . Cambridge University Press , New York . Eyal Kushilevitz and Noam Nisan. 1997. Communication Complexity. Cambridge University Press, New York."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-007-2160-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548308009656"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21924"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00493-012-2714-z"},{"key":"e_1_2_1_22_1","unstructured":"Shachar Lovett. 2013. Additive combinatorics and its applications in theoretical computer science. http:\/\/cseweb.ucsd.edu\/~slovett\/files\/addcomb-survey.pdf.  Shachar Lovett. 2013. Additive combinatorics and its applications in theoretical computer science. http:\/\/cseweb.ucsd.edu\/~slovett\/files\/addcomb-survey.pdf."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591799"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/800070.802208"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01192527"},{"key":"e_1_2_1_26_1","first-page":"323","article-title":"An analog of Freiman\u2019s theorem in groups","volume":"258","author":"Ruzsa Imre Z.","year":"1999","unstructured":"Imre Z. Ruzsa . 1999 . An analog of Freiman\u2019s theorem in groups . Ast\u00e8rique 258 , 323 -- 326 . Imre Z. Ruzsa. 1999. An analog of Freiman\u2019s theorem in groups. Ast\u00e8rique 258, 323--326.","journal-title":"Ast\u00e8rique"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250864"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548307008644"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.2140\/apde.2012.5.627"},{"key":"e_1_2_1_30_1","volume-title":"Cambridge University Press","author":"Tao Terence","unstructured":"Terence Tao and Van Vu. 2006. Additive Combinatorics . Cambridge University Press , Cambridge . Terence Tao and Van Vu. 2006. Additive Combinatorics. Cambridge University Press, Cambridge."},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1976.11994095"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629598","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629598","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T06:13:29Z","timestamp":1750227209000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629598"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7]]},"references-count":31,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["10.1145\/2629598"],"URL":"https:\/\/doi.org\/10.1145\/2629598","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7]]},"assertion":[{"value":"2012-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-07-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}