{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:06:58Z","timestamp":1750694818685,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":21,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"name":"NSF (National Science Foundation)","award":["2141536"],"award-info":[{"award-number":["2141536"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649607","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"630-639","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Communication Lower Bounds for Collision Problems via Density Increment Arguments"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9581-9593","authenticated-orcid":false,"given":"Guangxu","family":"Yang","sequence":"first","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6410-8649","authenticated-orcid":false,"given":"Jiapeng","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Southern California, Los Angeles, USA"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509999"},{"key":"e_1_3_2_1_2_1","unstructured":"Scott Aaronson Robin Kothari William Kretschmer and Justin Thaler. 2019. Quantum lower bounds for approximate counting via laurent polynomials. arXiv preprint arXiv:1904.08914."},{"key":"e_1_3_2_1_3_1","volume-title":"Proceedings, Part II 38","author":"Bauer Balthazar","year":"2018","unstructured":"Balthazar Bauer, Pooya Farshim, and Sogol Mazaheri. 2018. Combiners for backdoored random oracles. In Advances in Cryptology\u2013CRYPTO 2018: 38th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 19\u201323, 2018, Proceedings, Part II 38. 272\u2013302."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2134250"},{"key":"e_1_3_2_1_5_1","volume-title":"46th International Colloquium on Automata, Languages, and Programming (ICALP","author":"Chattopadhyay Arkadev","year":"2019","unstructured":"Arkadev Chattopadhyay, Yuval Filmus, Sajin Koroth, Or Meir, and Toniann Pitassi. 2019. Query-to-communication lifting for BPP using inner product. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-45724-2_15"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2484248"},{"key":"e_1_3_2_1_8_1","unstructured":"Mika G\u00f6\u00f6s and Siddhartha Jain. 2022. Communication Complexity of Collision. arXiv preprint arXiv:2208.00029."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.70"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.21"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.20"},{"key":"e_1_3_2_1_12_1","unstructured":"Mi-Ying (Miryam) Huang Xinyu Mao Guangxu Yang and Jiapeng Zhang. 2023. Communication Lower Bounds of Key-Agreement Protocols via Density Increment Arguments. Cryptology ePrint Archive Paper 2023\/1349. https:\/\/eprint.iacr.org\/2023\/1349"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.1994.316069"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2021.3"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.apal.2019.102722"},{"key":"e_1_3_2_1_16_1","first-page":"215","volume-title":"Leibniz international proceedings in informatics","author":"Lovett Shachar","year":"2022","unstructured":"Shachar Lovett, Raghu Meka, Ian Mertz, Toniann Pitassi, and Jiapeng Zhang. 2022. Lifting with sunflowers. Leibniz international proceedings in informatics, 215 (2022)."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-70500-2_2"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Shachar Lovett and Jiapeng Zhang. 2023. Streaming Lower Bounds and Asymmetric Set-Disjointness. arXiv preprint arXiv:2301.05658.","DOI":"10.1109\/FOCS57990.2023.00056"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/050643684"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/795663.796321"},{"key":"e_1_3_2_1_21_1","unstructured":"Guangxu Yang and Jiapeng Zhang. 2022. Simulation methods in communication complexity revisited. In Electron. Colloquium Comput. Complex. TR22-019."}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Vancouver BC Canada","acronym":"STOC '24"},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649607","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649607","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T16:36:46Z","timestamp":1750178206000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649607"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":21,"alternative-id":["10.1145\/3618260.3649607","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649607","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}