{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:16:17Z","timestamp":1759637777307,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":59,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316353","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"42-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["The log-approximate-rank conjecture is false"],"prefix":"10.1145","author":[{"given":"Arkadev","family":"Chattopadhyay","sequence":"first","affiliation":[{"name":"TIFR, India"}]},{"given":"Nikhil S.","family":"Mande","sequence":"additional","affiliation":[{"name":"Georgetown University, USA"}]},{"given":"Suhail","family":"Sherif","sequence":"additional","affiliation":[{"name":"TIFR, India"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897644"},{"volume-title":"APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, 2012. Proceedings. 338\u2013349","year":"2012","author":"Ada Anil","key":"e_1_3_2_1_2_1"},{"volume-title":"Separating Quantum Communication and Approximate Rank. In 32nd Computational Complexity Conference, CCC","year":"2017","author":"Anshu Anurag","key":"e_1_3_2_1_3_1"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Anurag Anshu Naresh Goud Boddu and Dave Touchette. 2018. Quantum Log-Approximate-Rank Conjecture is also False. arXiv preprint arXiv:1811.10525 (2018).  Anurag Anshu Naresh Goud Boddu and Dave Touchette. 2018. Quantum Log-Approximate-Rank Conjecture is also False. arXiv preprint arXiv:1811.10525 (2018).","DOI":"10.1109\/FOCS.2019.00063"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/100811969"},{"volume-title":"9th Innovations in Theoretical Computer Science Conference, ITCS 2018","year":"2018","author":"Braverman Mark","key":"e_1_3_2_1_6_1"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.86"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89585"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_3_2_1_10_1","unstructured":"Arkadev Chattopadhyay Michal Kouck\u00fd Bruno Loff and Sagnik Mukhopadhyay. 2017. Simulation Theorems via Pseudorandom Properties. CoRR abs\/1704.06807 (2017). http:\/\/arxiv.org\/abs\/1704.06807  Arkadev Chattopadhyay Michal Kouck\u00fd Bruno Loff and Sagnik Mukhopadhyay. 2017. Simulation Theorems via Pseudorandom Properties. CoRR abs\/1704.06807 (2017). http:\/\/arxiv.org\/abs\/1704.06807"},{"key":"e_1_3_2_1_11_1","unstructured":"Arkadev Chattopadhyay Nikhil Mande and Suhail Sherif. 2018.  Arkadev Chattopadhyay Nikhil Mande and Suhail Sherif. 2018."},{"key":"e_1_3_2_1_12_1","unstructured":"The Log-Approximate-Rank Conjecture is False. ECCC TR18-176 (2018).  The Log-Approximate-Rank Conjecture is False. ECCC TR18-176 (2018)."},{"key":"e_1_3_2_1_13_1","unstructured":"https:\/\/eccc. weizmann.ac.il\/report\/2018\/176  https:\/\/eccc. weizmann.ac.il\/report\/2018\/176"},{"key":"e_1_3_2_1_14_1","unstructured":"Ronald de Wolf. 2018. Private Communication.  Ronald de Wolf. 2018. Private Communication."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716307"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897535"},{"key":"e_1_3_2_1_17_1","unstructured":"Dmitry Gavinsky. 2016.  Dmitry Gavinsky. 2016."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897545"},{"volume-title":"41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 514\u2013524","year":"2014","author":"Gavinsky Dmitry","key":"e_1_3_2_1_19_1"},{"key":"e_1_3_2_1_20_1","first-page":"1","article-title":"Randomized Communication Vs. Partition Number. In Automata, Languages, and Programming - 44th International Colloquium on Automata, languages and Programming","volume":"52","author":"G\u00f6\u00f6s Mika","year":"2017","journal-title":"ICALP."},{"key":"e_1_3_2_1_21_1","unstructured":"Mika G\u00f6\u00f6s Toniann Pitassi and Thomas Watson. 2015.  Mika G\u00f6\u00f6s Toniann Pitassi and Thomas Watson. 2015."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"volume-title":"Query-to-Communication Lifting for BPP. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS. 132\u2013143","year":"2017","author":"G\u00f6\u00f6s Mika","key":"e_1_3_2_1_23_1"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-008-0654-y"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(96)00290-3"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1080\/01621459.1963.10500830"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.31"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0405044"},{"volume-title":"Rectangle Size Bounds and Threshold Covers in Communication Complexity. In 18th Annual IEEE Conference on Computational Complexity (Complexity 2003)","year":"2003","author":"Klauck Hartmut","key":"e_1_3_2_1_29_1"},{"volume-title":"41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I. 701\u2013712","year":"2014","author":"Kol Gillat","key":"e_1_3_2_1_30_1"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055438"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Matthias Krause. 1996. Geometric Arguments Yield Better Bounds for Threshold Circuits and Distributed Computing. Theor. Comput. Sci. 156 1&2 (1996) 99\u2013117.  Matthias Krause. 1996. Geometric Arguments Yield Better Bounds for Threshold Circuits and Distributed Computing. Theor. Comput. Sci. 156 1&2 (1996) 99\u2013117.","DOI":"10.1016\/0304-3975(95)00005-4"},{"key":"e_1_3_2_1_33_1","unstructured":"Eyal Kushilevitz and Noam Nisan. 1997.  Eyal Kushilevitz and Noam Nisan. 1997."},{"key":"e_1_3_2_1_34_1","unstructured":"Communication complexity. Cambridge University Press.  Communication complexity. Cambridge University Press."},{"key":"e_1_3_2_1_35_1","unstructured":"Troy Lee. 2012. Some Open Problems About Nonnegative Rank. http:\/\/research. cs.rutgers.edu\/~troyjlee\/open_problems.pdf.  Troy Lee. 2012. Some Open Problems About Nonnegative Rank. http:\/\/research. cs.rutgers.edu\/~troyjlee\/open_problems.pdf."},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.5555\/1803907"},{"volume-title":"Communication Complexity: A survey. In Paths, flows, and VLSI-layout","year":"1990","author":"Lov\u00e1sz L\u00e1szl\u00f3","key":"e_1_3_2_1_37_1"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21924"},{"key":"e_1_3_2_1_39_1","unstructured":"Shachar Lovett. 2014. Recent Advances on the Log-Rank Conjecture in Communication Complexity. Bulletin of the EATCS 112 (2014).  Shachar Lovett. 2014. Recent Advances on the Log-Rank Conjecture in Communication Complexity. Bulletin of the EATCS 112 (2014)."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2724704"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90157-D"},{"key":"e_1_3_2_1_42_1","unstructured":"Ryan O\u2019Donnell John Wright Yu Zhao Xiaorui Sun and Li-Yang Tan. 2014.  Ryan O\u2019Donnell John Wright Yu Zhao Xiaorui Sun and Li-Yang Tan. 2014."},{"volume-title":"Composition Theorem for Parity Kill Number. In IEEE 29th Conference on Computational Complexity, CCC 2014","year":"2014","author":"A","key":"e_1_3_2_1_43_1"},{"key":"e_1_3_2_1_44_1","unstructured":"144\u2013154.  144\u2013154."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90046-2"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(92)90260-M"},{"key":"e_1_3_2_1_47_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_3_2_1_48_1","unstructured":"Tom Sanders. 2018.  Tom Sanders. 2018."},{"key":"e_1_3_2_1_49_1","unstructured":"Boolean Functions with Small Spectral Norm Revisited. Arxiv (2018).  Boolean Functions with Small Spectral Norm Revisited. Arxiv (2018)."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-015-0110-y"},{"key":"e_1_3_2_1_51_1","unstructured":"Adi Shraibman. 2019.  Adi Shraibman. 2019."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"crossref","unstructured":"The corruption bound log-rank and communication complexity. Inf. Process. Lett. 141 (2019) 16\u201321.  The corruption bound log-rank and communication complexity. Inf. Process. Lett. 141 (2019) 16\u201321.","DOI":"10.1016\/j.ipl.2018.09.004"},{"key":"e_1_3_2_1_53_1","unstructured":"Makrand Sinha and Ronald de Wolf. 2018.  Makrand Sinha and Ronald de Wolf. 2018."},{"key":"e_1_3_2_1_54_1","unstructured":"Exponential Separation between Quantum Communication and Logarithm of Approximate Rank. arXiv preprint arXiv:1811.10090 (2018).  Exponential Separation between Quantum Communication and Logarithm of Approximate Rank. arXiv preprint arXiv:1811.10090 (2018)."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.76"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-34171-2_29"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90024-Y"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/800135.804414"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634210"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316353","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316353","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:32Z","timestamp":1750204472000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316353"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":59,"alternative-id":["10.1145\/3313276.3316353","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316353","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}