{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T02:48:57Z","timestamp":1767926937930,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":34,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,6,9]],"date-time":"2022-06-09T00:00:00Z","timestamp":1654732800000},"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":[[2022,6,9]]},"DOI":"10.1145\/3519935.3519969","type":"proceedings-article","created":{"date-parts":[[2022,6,10]],"date-time":"2022-06-10T15:29:32Z","timestamp":1654874972000},"page":"1284-1297","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["On the optimal time\/space tradeoff for hash tables"],"prefix":"10.1145","author":[{"given":"Michael A.","family":"Bender","sequence":"first","affiliation":[{"name":"Stony Brook University, USA"}]},{"given":"Mart\u00edn","family":"Farach-Colton","sequence":"additional","affiliation":[{"name":"Rutgers University, USA"}]},{"given":"John","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Yale University, USA"}]},{"given":"William","family":"Kuszmaul","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology, USA"}]},{"given":"Mingmou","family":"Liu","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2022,6,10]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02927-1_11"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.80"},{"key":"e_1_3_2_1_3_1","unstructured":"Michael A Bender Alex Conway Mart\u00edn Farach-Colton William Kuszmaul and Guido Tagliavini. 2021. All-Purpose Hashing. arXiv preprint arXiv:2109.04548.  Michael A Bender Alex Conway Mart\u00edn Farach-Colton William Kuszmaul and Guido Tagliavini. 2021. All-Purpose Hashing. arXiv preprint arXiv:2109.04548."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00026"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.14778\/2350229.2350275"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"Michael A Bender Mart\u00edn Farach-Colton John Kuszmaul and William Kuszmaul. 2021. On the Optimal Time\/Space Tradeoff for Hash Tables. arXiv preprint arXiv:2111.00602.  Michael A Bender Mart\u00edn Farach-Colton John Kuszmaul and William Kuszmaul. 2021. On the Optimal Time\/Space Tradeoff for Hash Tables. arXiv preprint arXiv:2111.00602.","DOI":"10.1145\/3519935.3519969"},{"key":"e_1_3_2_1_7_1","volume-title":"17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT","author":"Bercea Ioana O","year":"2020","unstructured":"Ioana O Bercea and Guy Even . 2020 . A Dynamic Space-Efficient Filter with Constant Time Operations . In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Ioana O Bercea and Guy Even. 2020. A Dynamic Space-Efficient Filter with Constant Time Operations. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/362686.362692"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/800133.804332"},{"key":"e_1_3_2_1_10_1","volume-title":"Latin American Symposium on Theoretical Informatics. 349\u2013361","author":"Demaine Erik D","unstructured":"Erik D Demaine , Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai P\u01cetra\u015fcu. 2006. De dictionariis dynamicis pauco spatio utentibus . In Latin American Symposium on Theoretical Informatics. 349\u2013361 . Erik D Demaine, Friedhelm Meyer auf der Heide, Rasmus Pagh, and Mihai P\u01cetra\u015fcu. 2006. De dictionariis dynamicis pauco spatio utentibus. In Latin American Symposium on Theoretical Informatics. 349\u2013361."},{"key":"e_1_3_2_1_11_1","volume-title":"Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP). 6\u201319","author":"Dietzfelbinger Martin","unstructured":"Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. 1990. A New Universal Class of Hash Functions and Dynamic Hashing in Real Time . In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP). 6\u201319 . Martin Dietzfelbinger and Friedhelm Meyer auf der Heide. 1990. A New Universal Class of Hash Functions and Dynamic Hashing in Real Time. In Proceedings of the 17th International Colloquium on Automata, Languages and Programming (ICALP). 6\u201319."},{"key":"e_1_3_2_1_12_1","volume-title":"H Rohnert, and RE Tarjan.","author":"Dietzfelbinger M","year":"1988","unstructured":"M Dietzfelbinger , A Karlin , K Mehlhorn , FM auf der Heide , H Rohnert, and RE Tarjan. 1988 . Dynamic perfect hashing: upper and lower bounds. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science (FOCS) . 524\u2013531. M Dietzfelbinger, A Karlin, K Mehlhorn, FM auf der Heide, H Rohnert, and RE Tarjan. 1988. Dynamic perfect hashing: upper and lower bounds. In [Proceedings 1988] 29th Annual Symposium on Foundations of Computer Science (FOCS). 524\u2013531."},{"key":"e_1_3_2_1_13_1","volume-title":"Proceedings of the 35th international colloquium on Automata, Languages and Programming (ICALP). 385\u2013396","author":"Dietzfelbinger Martin","year":"2008","unstructured":"Martin Dietzfelbinger and Rasmus Pagh . 2008 . Succinct Data Structures for Retrieval and Approximate Membership . In Proceedings of the 35th international colloquium on Automata, Languages and Programming (ICALP). 385\u2013396 . Martin Dietzfelbinger and Rasmus Pagh. 2008. Succinct Data Structures for Retrieval and Approximate Membership. In Proceedings of the 35th international colloquium on Automata, Languages and Programming (ICALP). 385\u2013396."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/11523468_14"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780634"},{"key":"e_1_3_2_1_16_1","unstructured":"Peter C Dillinger and Stefan Walzer. 2021. Ribbon filter: practically smaller than Bloom and Xor. arXiv preprint arXiv:2103.02515.  Peter C Dillinger and Stefan Walzer. 2021. Ribbon filter: practically smaller than Bloom and Xor. arXiv preprint arXiv:2103.02515."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2674005.2674994"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/646517.696322"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1382436.1382752"},{"key":"e_1_3_2_1_20_1","unstructured":"Don Knuth. 1963. Notes on \u00f6pen\" addressing.  Don Knuth. 1963. Notes on \u00f6pen\" addressing."},{"key":"e_1_3_2_1_21_1","volume-title":"The Art of Computer Programming, Volume III: Sorting and Searching","author":"Knuth Donald E.","unstructured":"Donald E. Knuth . 1973. The Art of Computer Programming, Volume III: Sorting and Searching . Addison-Wesley . isbn:0-201-03803-X Donald E. Knuth. 1973. The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley. isbn:0-201-03803-X"},{"key":"e_1_3_2_1_22_1","volume-title":"47th International Colloquium on Automata, Languages, and Programming (ICALP).","author":"Liu Mingmou","year":"2020","unstructured":"Mingmou Liu , Yitong Yin , and Huacheng Yu . 2020 . Succinct Filters for Sets of Unknown Sizes. In 47th International Colloquium on Automata, Languages, and Programming (ICALP). Mingmou Liu, Yitong Yin, and Huacheng Yu. 2020. Succinct Filters for Sets of Unknown Sizes. In 47th International Colloquium on Automata, Languages, and Programming (ICALP)."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.81"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/71.963420"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060606"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780633"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.5555\/1070432.1070548"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2003.12.002"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2013.17"},{"key":"e_1_3_2_1_31_1","volume-title":"Succincter. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 305\u2013313","author":"Patrascu Mihai","year":"2008","unstructured":"Mihai Patrascu . 2008 . Succincter. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 305\u2013313 . Mihai Patrascu. 2008. Succincter. In Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 305\u2013313."},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-45061-0_30"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63450"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384274"}],"event":{"name":"STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing","location":"Rome Italy","acronym":"STOC '22","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519969","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519935.3519969","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T17:49:38Z","timestamp":1750268978000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519935.3519969"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,6,9]]},"references-count":34,"alternative-id":["10.1145\/3519935.3519969","10.1145\/3519935"],"URL":"https:\/\/doi.org\/10.1145\/3519935.3519969","relation":{},"subject":[],"published":{"date-parts":[[2022,6,9]]},"assertion":[{"value":"2022-06-10","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}