{"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":1750695004845,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":95,"publisher":"ACM","funder":[{"name":"NSF (National Science Foundation)","award":["CCF 2247577, CCF 2106827, DMS 2023528"],"award-info":[{"award-number":["CCF 2247577, CCF 2106827, DMS 2023528"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,15]]},"DOI":"10.1145\/3717823.3718215","type":"proceedings-article","created":{"date-parts":[[2025,6,15]],"date-time":"2025-06-15T22:24:47Z","timestamp":1750026287000},"page":"268-277","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Optimal Non-oblivious Open Addressing"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-7639-530X","authenticated-orcid":false,"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, Stony Brook, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"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":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0095-0626","authenticated-orcid":false,"given":"Renfei","family":"Zhou","sequence":"additional","affiliation":[{"name":"Carnegie Mellon University, Pittsburgh, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,6,15]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/17.2.135"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_11"},{"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\/360715.360737"},{"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.1137\/1.9781611977936.33"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519969"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00115"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS61266.2024.00047"},{"key":"e_1_3_2_1_11_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 arxiv:2503.13628. 10.48550\/arXiv.2503.13628","DOI":"10.48550\/arXiv.2503.13628"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-022-01057-0"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.36"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/361952.361964"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISPAN.2005.47"},{"key":"e_1_3_2_1_16_1","volume-title":"Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 469\u2013476","author":"Cain Julie Anne","year":"2007","unstructured":"Julie Anne Cain, Peter Sanders, and Nick Wormald. 2007. The random graph threshold for k-orientiability and a fast algorithm for optimal multiple-choice allocation. In Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 469\u2013476."},{"volume-title":"Proc. 9th ACM Symposium on Theory of Computing (STOC). 106\u2013112","author":"Lawrence Carter J.","key":"e_1_3_2_1_17_1","unstructured":"J. Lawrence Carter and Mark N. Wegman. 1977. Universal classes of hash functions. In Proc. 9th ACM Symposium on Theory of Computing (STOC). 106\u2013112."},{"volume-title":"Proc. 26th IEEE Symposium on Foundations of Computer Science (SFCS). 281\u2013288","author":"Celis Pedro","key":"e_1_3_2_1_18_1","unstructured":"Pedro Celis, Per-Ake Larson, and J. Ian Munro. 1985. Robin Hood hashing. In Proc. 26th IEEE Symposium on Foundations of Computer Science (SFCS). 281\u2013288."},{"key":"e_1_3_2_1_19_1","volume-title":"Kane","author":"Cohen Jeffrey S.","year":"2009","unstructured":"Jeffrey S. Cohen and Daniel M. Kane. 2009. Bounds on the independence required for cuckoo hashing. ACM Transactions on Algorithms."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.39"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/11682462_34"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_19"},{"volume-title":"Proc. 17th International Colloquium on Automata, Languages, and Programming (ICALP). 6\u201319","author":"Dietzfelbinger Martin","key":"e_1_3_2_1_23_1","unstructured":"Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. 1990. A new universal class of hash functions and dynamic hashing in real time. In Proc. 17th International Colloquium on Automata, Languages, and Programming (ICALP). 6\u201319."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_30"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.02.054"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/17.4.340"},{"key":"e_1_3_2_1_27_1","volume-title":"Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS).","author":"Farach-Colton Mart\u00edn","year":"2024","unstructured":"Mart\u00edn Farach-Colton, Andrew Krapivin, and William Kuszmaul. 2024. Tight Bounds for Open Addressing Without Reordering. In Proc. 65th IEEE Symposium on Foundations of Computer Science (FOCS)."},{"key":"e_1_3_2_1_28_1","volume-title":"Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 459\u2013468","author":"Fernholz Daniel","year":"2007","unstructured":"Daniel Fernholz and Vijaya Ramachandran. 2007. The k-orientability thresholds for G_n, p. In Proc. 18th ACM-SIAM Symposium on Discrete Algorithms (SODA). 459\u2013468."},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222001"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146591"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0963548315000334"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_30"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/100797503"},{"key":"e_1_3_2_1_34_1","volume-title":"Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 670\u2013678","author":"Franceschini Gianni","year":"2003","unstructured":"Gianni Franceschini and Roberto Grossi. 2003. Implicit dictionaries supporting searches and amortized updates in O(log n log log n) time. In Proc. 14th ACM-SIAM Symposium on Discrete Algorithms (SODA). 670\u2013678."},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.5555\/1759210.1759244"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-005-1167-9"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2002.1181891"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/322358.322364"},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20808"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20427"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/090770928"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2017.11.010"},{"volume-title":"Interpolation and Interpolation Hash Searching. Department of Computer Science","author":"Gonnet Gaston H.","key":"e_1_3_2_1_43_1","unstructured":"Gaston H. Gonnet. 1977. Interpolation and Interpolation Hash Searching. Department of Computer Science, University of Waterloo."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208038"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-34862-4_15"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90046-6"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2001.1171"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl"},{"key":"e_1_3_2_1_49_1","volume-title":"Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA). 570\u2013582","author":"Iacono John","year":"2012","unstructured":"John Iacono and Mihai P\u01cetra\u015fcu. 2012. Using Hashing to Solve the Dictionary Problem. In Proc. 23rd ACM-SIAM Symposium on Discrete Algorithms (SODA). 570\u2013582."},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-007-9155-x"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-019-00595-4"},{"key":"e_1_3_2_1_52_1","volume-title":"Proc. 45th Allerton Conference on Communication, Control, and Computing (Allerton). 75","author":"Kirsch Adam","year":"2007","unstructured":"Adam Kirsch and Michael Mitzenmacher. 2007. Using a queue to de-amortize cuckoo hashing in hardware. In Proc. 45th Allerton Conference on Communication, Control, and Computing (Allerton). 75."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1137\/080728743"},{"key":"e_1_3_2_1_54_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_55_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","year":"2018","unstructured":"Donald E. Knuth. 1998. The Art of Computer Programming, Volume III: Sorting and Searching (2nd ed.). Addison-Wesley. isbn:0201896850 https:\/\/www.worldcat.org\/oclc\/312994415","edition":"2"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/0114101"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00097"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00111"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.133"},{"key":"e_1_3_2_1_60_1","volume-title":"Proc. 51st International Colloquium on Automata, Languages, and Programming (ICALP).","author":"Kuszmaul William","year":"2024","unstructured":"William Kuszmaul and Zoe Xi. 2024. Towards an Analysis of Quadratic Probing. In Proc. 51st International Colloquium on Automata, Languages, and Programming (ICALP)."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-04128-0_60"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.23"},{"key":"e_1_3_2_1_63_1","volume-title":"Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS). 1715\u20131733","author":"Li Tianxiao","year":"2023","unstructured":"Tianxiao Li, Jingxun Liang, Huacheng Yu, and Renfei Zhou. 2023. Dynamic \u201cSuccincter\u201d. In Proc. 64th IEEE Symposium on Foundations of Computer Science (FOCS). 1715\u20131733."},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS57990.2023.00112"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.9"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62246"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/20.2.137"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054103002242"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/357980.357995"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1109\/Allerton.2012.6483344"},{"volume-title":"Analysis and design of algorithms: Double hashing and parallel graph searching","author":"Molodowitch Mariko","key":"e_1_3_2_1_71_1","unstructured":"Mariko Molodowitch. 1990. Analysis and design of algorithms: Double hashing and parallel graph searching. University of California, Irvine."},{"key":"e_1_3_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(80)90037-9"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1984.715937"},{"key":"e_1_3_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90043-7"},{"key":"e_1_3_2_1_75_1","volume-title":"Proc. 1986 ACM Fall joint computer conference. 601\u2013610","author":"Ian Munro J.","year":"1986","unstructured":"J. Ian Munro and Pedro Celis. 1986. Techniques for collision resolution in hash tables with open addressing. In Proc. 1986 ACM Fall joint computer conference. 601\u2013610."},{"key":"e_1_3_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380844"},{"key":"e_1_3_2_1_77_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780633"},{"key":"e_1_3_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1137\/070702278"},{"key":"e_1_3_2_1_79_1","volume-title":"Cuckoo Hashing. In Proc. 9th European Symposium on Algorithms (ESA). 121\u2013133","author":"Pagh Rasmus","year":"2001","unstructured":"Rasmus Pagh and Flemming Friche Rodler. 2001. Cuckoo Hashing. In Proc. 9th European Symposium on Algorithms (ESA). 121\u2013133."},{"key":"e_1_3_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2014.26"},{"key":"e_1_3_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/2716317"},{"key":"e_1_3_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362036"},{"key":"e_1_3_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_30"},{"key":"e_1_3_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1145\/1328911.1328912"},{"key":"e_1_3_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63450"},{"key":"e_1_3_2_1_86_1","unstructured":"Alan Siegel. 1995. On universal classes of extremely random constant time hash functions and their time-space tradeoff. Technical Report TR1995-684 New York University."},{"key":"e_1_3_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539701386216"},{"key":"e_1_3_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1991.185427"},{"key":"e_1_3_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.1145\/321707.321722"},{"key":"e_1_3_2_1_90_1","doi-asserted-by":"publisher","DOI":"10.1137\/110842211"},{"key":"e_1_3_2_1_91_1","volume-title":"Proc. 30th European Symposium on Algorithms (ESA). 87:1\u201387:11","author":"Walzer Stefan","year":"2022","unstructured":"Stefan Walzer. 2022. Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold. In Proc. 30th European Symposium on Algorithms (ESA). 87:1\u201387:11."},{"key":"e_1_3_2_1_92_1","doi-asserted-by":"publisher","DOI":"10.1145\/3589558"},{"volume-title":"Proc. 20th IEEE Symposium on Foundations of Computer Science (FOCS). 175\u2013182","author":"Wegman Mark N.","key":"e_1_3_2_1_93_1","unstructured":"Mark N. Wegman and J. Lawrence Carter. 1979. New classes and applications of hash functions. In Proc. 20th IEEE Symposium on Foundations of Computer Science (FOCS). 175\u2013182."},{"key":"e_1_3_2_1_94_1","doi-asserted-by":"publisher","DOI":"10.1145\/322261.322274"},{"key":"e_1_3_2_1_95_1","doi-asserted-by":"publisher","DOI":"10.1145\/3828.3836"}],"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.3718215","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,23]],"date-time":"2025-06-23T15:44:06Z","timestamp":1750693446000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3717823.3718215"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,15]]},"references-count":95,"alternative-id":["10.1145\/3717823.3718215","10.1145\/3717823"],"URL":"https:\/\/doi.org\/10.1145\/3717823.3718215","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"}}]}}