{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:30:06Z","timestamp":1759638606066,"version":"3.41.0"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T00:00:00Z","timestamp":1592697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001502","name":"Department of Atomic Energy, Government of India","doi-asserted-by":"crossref","award":["12-R8D-TFR-5.01-0500"],"award-info":[{"award-number":["12-R8D-TFR-5.01-0500"]}],"id":[{"id":"10.13039\/501100001502","id-type":"DOI","asserted-by":"crossref"}]},{"name":"DAE fellowship"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>\n            We construct a simple and total Boolean function\n            <jats:italic>F<\/jats:italic>\n            =\n            <jats:italic>f<\/jats:italic>\n            \u25cb XOR on 2\n            <jats:italic>n<\/jats:italic>\n            variables that has only\n            <jats:italic>O<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) spectral norm,\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ) approximate rank, and\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2.5<\/jats:sup>\n            ) approximate nonnegative rank. We show it has polynomially large randomized bounded-error communication complexity of \u03a9(\u221a\n            <jats:italic>n<\/jats:italic>\n            ). This yields the first exponential gap between the logarithm of the approximate rank and randomized communication complexity for total functions. Thus,\n            <jats:italic>F<\/jats:italic>\n            witnesses a refutation of the log-approximate-rank conjecture that was posed by Lee and Shraibman as a very natural analogue for randomized communication of the still unresolved log-rank conjecture for deterministic communication. The best known previous gap for any total function between the two measures is a recent 4th-power separation by G\u00f6\u00f6s et al.\n          <\/jats:p>\n          <jats:p>\n            Additionally, our function\n            <jats:italic>F<\/jats:italic>\n            refutes Grolmusz\u2019s conjecture\u00a0and a variant of the log-approximate-nonnegative-rank conjecture suggested recently by Kol et\u00a0al., both of which are implied by the log-approximate-rank conjecture. The complement of\n            <jats:italic>F<\/jats:italic>\n            has exponentially large approximate nonnegative rank. This answers a question of Lee [32], showing that approximate nonnegative rank can be exponentially larger than approximate rank. The inner function\n            <jats:italic>F<\/jats:italic>\n            also falsifies a conjecture about parity measures of Boolean functions made by Tsang et al. The latter conjecture implied the log-rank conjecture for XOR functions.\n          <\/jats:p>\n          <jats:p>\n            We are pleased to note that shortly after we published our results, two independent groups of researchers, Anshu et al. and Sinha and de Wolf, used our function\n            <jats:italic>F<\/jats:italic>\n            to prove that the quantum-log-rank conjecture is also false by showing that\n            <jats:italic>F<\/jats:italic>\n            has \u03a9(\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>1\/6<\/jats:sup>\n            ) quantum communication complexity.\n          <\/jats:p>","DOI":"10.1145\/3396695","type":"journal-article","created":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T02:48:55Z","timestamp":1592794135000},"page":"1-28","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["The Log-Approximate-Rank Conjecture Is False"],"prefix":"10.1145","volume":"67","author":[{"given":"Arkadev","family":"Chattopadhyay","sequence":"first","affiliation":[{"name":"Tata Institute of Fundamental Research, Colaba, Mumbai, India"}]},{"given":"Nikhil S.","family":"Mande","sequence":"additional","affiliation":[{"name":"Georgetown University, Washington DC, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0554-933X","authenticated-orcid":false,"given":"Suhail","family":"Sherif","sequence":"additional","affiliation":[{"name":"Tata Institute of Fundamental Research, Colaba, Mumbai, India"}]}],"member":"320","published-online":{"date-parts":[[2020,6,21]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897644"},{"key":"e_1_2_1_2_1","doi-asserted-by":"crossref","unstructured":"Anil Ada Omar Fawzi and Hamed Hatami. 2012. Spectral norm of symmetric functions. In Proceedings of the15th International Workshop on Approximation Randomization and Combinatorial Optimization: Algorithms and Techniques (APPROX\u201912) and the 16th International Workshop on Randomization and Computation (RANDOM\u201912).338--349.  Anil Ada Omar Fawzi and Hamed Hatami. 2012. Spectral norm of symmetric functions. In Proceedings of the15th International Workshop on Approximation Randomization and Combinatorial Optimization: Algorithms and Techniques (APPROX\u201912) and the 16th International Workshop on Randomization and Computation (RANDOM\u201912).338--349.","DOI":"10.1007\/978-3-642-32512-0_29"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3135595.3135619"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00063"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811969"},{"volume-title":"Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS\u201918)","year":"2018","author":"Braverman Mark","key":"e_1_2_1_6_1"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.86"},{"volume-title":"Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS\u201990)","year":"1990","author":"Bruck Jehoshua","key":"e_1_2_1_8_1"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_2_1_10_1","unstructured":"Arkadev Chattopadhyay Michal Kouck\u00fd Bruno Loff and Sagnik Mukhopadhyay. 2017. Simulation theorems via pseudorandom properties. arXiv:1704.06807.  Arkadev Chattopadhyay Michal Kouck\u00fd Bruno Loff and Sagnik Mukhopadhyay. 2017. Simulation theorems via pseudorandom properties. arXiv:1704.06807."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90001-1"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716307"},{"key":"e_1_2_1_14_1","first-page":"19","article-title":"Upper Bounds on Communication in Terms of Approximate Rank","author":"G\u00e1l Anna","year":"2019","journal-title":"ECCC Report TR"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2907939"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897545"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_43"},{"volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP\u201917)","year":"2017","author":"G\u00f6\u00f6s Mika","key":"e_1_2_1_18_1"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.21"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-008-0654-y"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00290-3"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1136869"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.31"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2003.1214415"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-43948-7_58"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055438"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00005-4"},{"volume-title":"Communication Complexity","author":"Kushilevitz Eyal","key":"e_1_2_1_31_1"},{"volume-title":"Retrieved","year":"2012","author":"Lee Troy","key":"e_1_2_1_32_1"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.5555\/1803907"},{"volume-title":"Paths, Flows, and VLSI-Layout","author":"Lov\u00e1sz L\u00e1szl\u00f3","key":"e_1_2_1_35_1"},{"volume-title":"Proceedings of the 29th Annual Symposium on Foundations of Computer Science (FOCS\u201988)","author":"Lov\u00e1sz L\u00e1szl\u00f3","key":"e_1_2_1_36_1"},{"key":"e_1_2_1_37_1","first-page":"1","article-title":"Recent advances on the log-rank conjecture in communication complexity","volume":"112","author":"Lovett Shachar","year":"2014","journal-title":"Bulletin of the EATCS"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/2724704"},{"key":"e_1_2_1_39_1","unstructured":"Ashley Montanaro and Tobias Osborne. 2009. On the communication complexity of XOR functions. arXiv:0909.3392.  Ashley Montanaro and Tobias Osborne. 2009. On the communication complexity of XOR functions. arXiv:0909.3392."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.22"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90046-2"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.07.012"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_2_1_45_1","first-page":"145","article-title":"Quantum communication complexity of symmetric predicates. Izvestia","volume":"67","author":"Razborov Alexander A.","year":"2003","journal-title":"Mathematics"},{"key":"e_1_2_1_46_1","unstructured":"Tom Sanders. 2018. Boolean functions with small spectral norm revisited. arXiv:1804.04050.  Tom Sanders. 2018. Boolean functions with small spectral norm revisited. arXiv:1804.04050."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0110-y"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2018.09.004"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00062"},{"volume-title":"Proceedings of the 19th Annual IEEE Conference on Computational Complexity (CCC\u201904)","year":"2004","author":"Sun Xiaoming","key":"e_1_2_1_50_1"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.76"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-34171-2_29"},{"key":"e_1_2_1_53_1","unstructured":"Ronald de Wolf. 2018. Private communication.  Ronald de Wolf. 2018. Private communication."},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"},{"volume-title":"Proceedings of the 11th Annual ACM Symposium on Theory of Computing (STOC\u201979)","year":"1979","author":"Chi-Chih Yao Andrew","key":"e_1_2_1_55_1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.136"},{"volume-title":"Communication complexities of symmetric XOR functions. Quantum Information 8 Computation 9, 3","year":"2009","author":"Zhang Zhiqiang","key":"e_1_2_1_57_1"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396695","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3396695","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:33:28Z","timestamp":1750199608000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3396695"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,21]]},"references-count":55,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3396695"],"URL":"https:\/\/doi.org\/10.1145\/3396695","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2020,6,21]]},"assertion":[{"value":"2019-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-06-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}