{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T16:10:04Z","timestamp":1750695004775,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":50,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CCF-2008733"],"award-info":[{"award-number":["CCF-2008733"]}]},{"name":"Simons Foundation","award":["#491119"],"award-info":[{"award-number":["#491119"]}]},{"name":"Israel Science Foundation","award":["#3011005535"],"award-info":[{"award-number":["#3011005535"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718300","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T23:34:42Z","timestamp":1750030482000},"page":"256-267","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["A Framework for Building Data Structures from Communication Protocols"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0004-8042-0976","authenticated-orcid":false,"given":"Alexandr","family":"Andoni","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-2226-7980","authenticated-orcid":false,"given":"Shunhua","family":"Jiang","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9357-2299","authenticated-orcid":false,"given":"Omri","family":"Weinstein","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"},{"name":"Hebrew University of Jerusalem, Jerusalem, Israel"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.12"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (SODA","author":"Abboud Amir","year":"2014","unstructured":"Amir Abboud, Ryan Williams, and Huacheng Yu. 2014. More applications of the polynomial method to algorithm design. In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms (SODA 2014). 218\u2013230."},{"volume-title":"Range searching","author":"Agarwal Pankaj K.","key":"e_1_3_2_1_3_1","unstructured":"Pankaj K. Agarwal. 1997. Range searching. CRC Press, Inc., USA. 575\u2013598. isbn:0849385245"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00073"},{"key":"e_1_3_2_1_5_1","volume-title":"Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems. In SIAM Symposium on Simplicity in Algorithms (SOSA).","author":"Alman Josh","year":"2025","unstructured":"Josh Alman, Alexandr Andoni, and Hengjie Zhang. 2025. Faster Algorithms for Average-Case Orthogonal Vectors and Closest Pair Problems. In SIAM Symposium on Simplicity in Algorithms (SOSA)."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2016.57"},{"key":"e_1_3_2_1_7_1","unstructured":"Alexandr Andoni and David Cheikhi. 2021. From Average Embeddings To Nearest Neighbor Search. arXiv preprint arXiv:2105.05761."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973402.76"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3039686.3039690"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188846"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.72"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746553"},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the ACM Symposium on Computational Geometry (SoCG). Available at arxiv:1507","author":"Andoni Alexandr","year":"2016","unstructured":"Alexandr Andoni and Ilya Razenshteyn. 2016. Tight Lower Bounds for Data-Dependent Locality-Sensitive Hashing. In Proceedings of the ACM Symposium on Computational Geometry (SoCG). Available at arxiv:1507.04299"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1986.15"},{"volume-title":"Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC \u201997)","author":"Babai L\u00e1szl\u00f3","key":"e_1_3_2_1_15_1","unstructured":"L\u00e1szl\u00f3 Babai, Paul Kimmel, and S. Venkatesh Lokam. 1997. On the distributional complexity of disjointness. In Proceedings of the 12th Annual IEEE Conference on Computational Complexity (CCC \u201997). 304\u2013315."},{"key":"e_1_3_2_1_16_1","unstructured":"Yiqiao Bao Anubhav Baweja Nicolas Menand Erik Waingarten Nathan White and Tian Zhang. 2024. Average-Distortion Sketching. arxiv:2411.05156. arxiv:2411.05156"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2002.1831"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301330"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.05.003"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00454-019-00062-5"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch87"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"crossref","unstructured":"Moses Charikar Piotr Indyk and Rina Panigrahy. 2002. New algorithms for subset query partial match orthogonal range searching and related problems. In International Colloquium on Automata Languages and Programming. 451\u2013462.","DOI":"10.1007\/3-540-45465-9_39"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00025"},{"key":"e_1_3_2_1_24_1","unstructured":"Lijie Chen. 2018. On The Hardness of Approximate and Exact (Bichromatic) Maximum Inner Product. Electron. Colloquium Comput. Complex. 26. https:\/\/eccc.weizmann.ac.il\/report\/2018\/026"},{"volume-title":"Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. 10th Innovations in Theoretical Computer Science","author":"Chen Lijie","key":"e_1_3_2_1_25_1","unstructured":"Lijie Chen and Ruosong Wang. 2019. Classical Algorithms from Quantum and Arthur-Merlin Communication Protocols. 10th Innovations in Theoretical Computer Science."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055443"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch142"},{"key":"e_1_3_2_1_28_1","volume-title":"Proceedings of the Symposium on Theory of Computing (STOC). 91\u2013100","author":"Cole Richard","year":"2004","unstructured":"Richard Cole, Lee-Ad Gottlieb, and Moshe Lewenstein. 2004. Dictionary matching and indexing with errors and don\u2019t cares. In Proceedings of the Symposium on Theory of Computing (STOC). 91\u2013100."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/365411.365791"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","unstructured":"Anja Feldmann and S. Muthukrishnan. 2000. Tradeoffs for Packet Classification. In Proceedings IEEE INFOCOM 2000 The Conference on Computer Communications Nineteenth Annual Joint Conference of the IEEE Computer and Communications Societies Reaching the Promised Land of Communications Tel Aviv Israel March 26-30 2000. IEEE Computer Society 1193\u20131202. https:\/\/doi.org\/10.1109\/INFCOM.2000.832493 10.1109\/INFCOM.2000.832493","DOI":"10.1109\/INFCOM.2000.832493"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196275"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/2688073.2688074"},{"key":"e_1_3_2_1_33_1","volume-title":"Data Mining: Concepts and Techniques","author":"Han Jiawei","year":"2011","unstructured":"Jiawei Han, Micheline Kamber, and Jian Pei. 2011. Data Mining: Concepts and Techniques (3rd ed.). Morgan Kaufmann Publishers Inc., San Francisco, CA, USA. isbn:0123814790","edition":"3"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746609"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1774"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1998.743438"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276876"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2020.74"},{"key":"e_1_3_2_1_39_1","volume-title":"37th International Symposium on Computational Geometry (SoCG","author":"Kush Deepanshu","year":"2021","unstructured":"Deepanshu Kush, Aleksandar Nikolov, and Haohua Tang. 2021. Near Neighbor Search via Efficient Average Distortion Embeddings. In 37th International Symposium on Computational Geometry (SoCG 2021)."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539798347177"},{"volume-title":"Lower bound techniques for data structures. Ph. D. Dissertation","author":"Patrascu Mihai","key":"e_1_3_2_1_41_1","unstructured":"Mihai Patrascu. 2008. Lower bound techniques for data structures. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/09075336X"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.86"},{"key":"e_1_3_2_1_44_1","unstructured":"Ronald Linn Rivest. 1974. Analysis of associative retrieval algorithms. PhD thesis."},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188916"},{"key":"e_1_3_2_1_46_1","volume-title":"The Design and Analysis of Spatial Data Structures","author":"Samet Hanan","year":"2015","unstructured":"Hanan Samet. 1990. The Design and Analysis of Spatial Data Structures. Addison-Wesley Longman Publishing Co., Inc., USA. isbn:0201502550"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/316188.316216"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2728167"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.09.023"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1142\/9789813272880_0188"}],"event":{"name":"STOC '25: 57th Annual ACM Symposium on Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Prague Czechia","acronym":"STOC '25"},"container-title":["Proceedings of the 57th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3717823.3718300","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:49:44Z","timestamp":1750693784000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718300"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":50,"alternative-id":["10.1145\/3717823.3718300","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718300","relation":{},"subject":[],"published":{"date-parts":[[2025,6,15]]},"assertion":[{"value":"2025-06-15","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}