{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:21Z","timestamp":1781031441042,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":47,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["CNS2504471"],"award-info":[{"award-number":["CNS2504471"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000008","name":"David and Lucile Packard Foundation","doi-asserted-by":"publisher","award":["2020-71730"],"award-info":[{"award-number":["2020-71730"]}],"id":[{"id":"10.13039\/100000008","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800823","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1116-1127","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Greedy Open Addressing Revisited: Beyond Yao\u2019s Lower Bound"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3616-7788","authenticated-orcid":false,"given":"Mart\u00edn","family":"Farach-Colton","sequence":"first","affiliation":[{"name":"New York University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0003-0227-7660","authenticated-orcid":false,"given":"Andrew","family":"Krapivin","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3855-3036","authenticated-orcid":false,"given":"William","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(78)90014-5"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/17.2.135"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.80"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/362790.362797"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00017"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3625817"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519969"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00115"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00047"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","unstructured":"Michael A. Bender William Kuszmaul and Renfei Zhou. 2025. Optimal Non-Oblivious Open Addressing. Preprint arXiv:2503.13628. https:\/\/doi.org\/10.48550\/arXiv.2503.13628 10.48550\/arXiv.2503.13628","DOI":"10.48550\/arXiv.2503.13628"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00046"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/361952.361964"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.48"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2018.39"},{"key":"e_1_3_2_1_15_1","volume-title":"Computational analysis of the random components induced by a binary equivalence relation. Ph. D. Dissertation","author":"Balbine Guy De","unstructured":"Guy De Balbine. 1968. Computational analysis of the random components induced by a binary equivalence relation. Ph. D. Dissertation. California Institute of Technology."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_19"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00045"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222001"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/S00224-004-1195-X"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20808"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/090770928"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.11.010"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34862-4_15"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90046-6"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.48"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9155-x"},{"key":"e_1_3_2_1_28_1","unstructured":"Donald E. Knuth. 1963. Notes on \u201copen\u201d addressing. Available online at. https:\/\/jeffe.cs.illinois.edu\/teaching\/datastructures\/2011\/notes\/knuth-OALP.pdf"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1974.11993556"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114101"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00097"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.133"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ICALP.2024.103"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00112"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.9"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62246"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/362851.362880"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44676-1_10"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1147\/RD.12.0130"},{"key":"e_1_3_2_1_40_1","volume-title":"Poblete and Alfredo Viola","author":"Patricio","year":"2016","unstructured":"Patricio V. Poblete and Alfredo Viola. 2016. Robin Hood Hashing really has constant average search cost and variance in full tables. CoRR, abs\/1605.04031 (2016)."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_30"},{"key":"e_1_3_2_1_42_1","volume-title":"Lecture 5: Coupon Collector","author":"Smyrnis Georgios","year":"2021","unstructured":"Georgios Smyrnis, Ryan Chhong, and Eric Price. 2021. Lecture 5: Coupon Collector; Balls and Bins. https:\/\/www.cs.utexas.edu\/ ecprice\/courses\/randomized\/fa21\/scribe\/lec5.pdf CS 388R: Randomized Algorithms, University of Texas at Austin, Fall 2021 lecture notes"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/362851.362882"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/321707.321722"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.ESA.2022.87"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","unstructured":"Philipp Woelfel. 2006. Maintaining External Memory Efficient Hash Tables. In Approximation Randomization and Combinatorial Optimization. Algorithms and Techniques 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems APPROX 2006 and 10th International Workshop on Randomization and Computation RANDOM 2006 Barcelona Spain August 28-30 2006 Proceedings Josep D\u00edaz Klaus Jansen Jos\u00e9 D. P. Rolim and Uri Zwick (Eds.) (Lecture Notes in Computer Science). Springer 508\u2013519. https:\/\/doi.org\/10.1007\/11830924_46 10.1007\/11830924_46","DOI":"10.1007\/11830924_46"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3836"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800823","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800823","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:02:25Z","timestamp":1781028145000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800823"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":47,"alternative-id":["10.1145\/3798129.3800823","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800823","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}