{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:49:01Z","timestamp":1781077741322,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":27,"publisher":"ACM","license":[{"start":{"date-parts":[[2020,6,22]],"date-time":"2020-06-22T00:00:00Z","timestamp":1592784000000},"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":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384274","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1389-1401","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Nearly optimal static Las Vegas succinct dictionary"],"prefix":"10.1145","author":[{"given":"Huacheng","family":"Yu","sequence":"first","affiliation":[{"name":"Princeton University, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488707"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294165"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539702405292"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(79)90044-8"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806771"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222001"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146591"},{"key":"e_1_3_2_1_8_1","volume-title":"4th International Workshop, WADS '95, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings. 482-493","author":"Faith","unstructured":"Faith E. Fich and Peter Bro Miltersen. 1995. Tables Should Be Sorted (On Random Access Machines). In Algorithms and Data Structures , 4th International Workshop, WADS '95, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings. 482-493 . Faith E. Fich and Peter Bro Miltersen. 1995. Tables Should Be Sorted (On Random Access Machines). In Algorithms and Data Structures, 4th International Workshop, WADS '95, Kingston, Ontario, Canada, August 16-18, 1995, Proceedings. 482-493."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/828.1884"},{"key":"e_1_3_2_1_10_1","volume-title":"More Haste","author":"Grossi Roberto","year":"2009","unstructured":"Roberto Grossi , Alessio Orlandi , Rajeev Raman , and S. Srinivasa Rao . 2009. More Haste , Less Waste : Lowering the Redundancy in Fully Indexable Dictionaries. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009 , February 26-28, 2009, Freiburg, Germany, Proceedings . 517-528. Roberto Grossi, Alessio Orlandi, Rajeev Raman, and S. Srinivasa Rao. 2009. More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings. 517-528."},{"key":"e_1_3_2_1_11_1","first-page":"549","volume-title":"Space-eficient Static Trees and Graphs. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park","author":"Jacobson Guy","year":"1989","unstructured":"Guy Jacobson . 1989 . Space-eficient Static Trees and Graphs. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park , North Carolina, USA , 30 October-1 November 1989. 549 - 554 . Guy Jacobson. 1989. Space-eficient Static Trees and Graphs. In 30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October-1 November 1989. 549-554."},{"key":"e_1_3_2_1_12_1","first-page":"442","volume-title":"23rd International Colloquium, ICALP96","author":"Miltersen Peter Bro","year":"1996","unstructured":"Peter Bro Miltersen . 1996 . Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication. In Automata, Languages and Programming , 23rd International Colloquium, ICALP96 , Paderborn, Germany , 8-12 July 1996, Proceedings. 442 - 453 . Peter Bro Miltersen. 1996. Lower Bounds for Static Dictionaries on RAMs with Bit Operations But No Multiplication. In Automata, Languages and Programming, 23rd International Colloquium, ICALP96, Paderborn, Germany, 8-12 July 1996, Proceedings. 442-453."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"e_1_3_2_1_14_1","volume-title":"The Design of Dynamic Data Structures","author":"Overmars Mark H.","unstructured":"Mark H. Overmars . 1983. The Design of Dynamic Data Structures . Springer-Verlag . Mark H. Overmars. 1983. The Design of Dynamic Data Structures. Springer-Verlag."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/380752.380836"},{"key":"e_1_3_2_1_17_1","volume-title":"Succincter. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). 305-313","author":"Pa\u02c7tra\u015fcu Mihai","year":"2008","unstructured":"Mihai Pa\u02c7tra\u015fcu . 2008 . Succincter. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). 305-313 . Mihai Pa\u02c7tra\u015fcu. 2008. Succincter. In Proc. 49th IEEE Symposium on Foundations of Computer Science (FOCS). 305-313."},{"key":"e_1_3_2_1_18_1","first-page":"232","volume-title":"Proceedings of the 38th Annual ACM Symposium on Theory of Computing","author":"Pa\u02c7tra\u015fcu Mihai","year":"2006","unstructured":"Mihai Pa\u02c7tra\u015fcu and Mikkel Thorup . 2006 . Time-space trade-ofs for predecessor search . In Proceedings of the 38th Annual ACM Symposium on Theory of Computing , Seattle, WA, USA , May 21-23, 2006. 232 - 240 . Mihai Pa\u02c7tra\u015fcu and Mikkel Thorup. 2006. Time-space trade-ofs for predecessor search. In Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006. 232-240."},{"key":"e_1_3_2_1_19_1","first-page":"555","volume-title":"Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007","author":"Pa\u02c7tra\u015fcu Mihai","year":"2007","unstructured":"Mihai Pa\u02c7tra\u015fcu and Mikkel Thorup . 2007 . Randomization does not help searching predecessors . In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007 , New Orleans, Louisiana, USA , January 7-9, 2007. 555 - 564 . Mihai Pa\u02c7tra\u015fcu and Mikkel Thorup. 2007. Randomization does not help searching predecessors. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007. 555-564."},{"key":"e_1_3_2_1_20_1","first-page":"117","volume-title":"Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010","author":"Pa\u02c7tra\u015fcu Mihai","year":"2010","unstructured":"Mihai Pa\u02c7tra\u015fcu and Emanuele Viola . 2010 . Cell-Probe Lower Bounds for Succinct Partial Sums . In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010 , Austin, Texas, USA , January 17-19, 2010. 117 - 122 . Mihai Pa\u02c7tra\u015fcu and Emanuele Viola. 2010. Cell-Probe Lower Bounds for Succinct Partial Sums. In Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010. 117-122."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1290672.1290680"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0219054"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Robert Endre Tarjan and Andrew Chi-Chih Yao. 1979. Storing a Sparse Table. Commun. ACM 22 11 ( 1979 ) 606-611.  Robert Endre Tarjan and Andrew Chi-Chih Yao. 1979. Storing a Sparse Table. Commun. ACM 22 11 ( 1979 ) 606-611.","DOI":"10.1145\/359168.359175"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/090766619"},{"key":"e_1_3_2_1_25_1","volume-title":"How to Store a Random Walk. CoRR abs\/","author":"Viola Emanuele","year":"1907","unstructured":"Emanuele Viola , Omri Weinstein , and Huacheng Yu. 2019. How to Store a Random Walk. CoRR abs\/ 1907 .10874 ( 2019 ). http:\/\/arxiv.org\/abs\/ 1907.10874 Emanuele Viola, Omri Weinstein, and Huacheng Yu. 2019. How to Store a Random Walk. CoRR abs\/ 1907.10874 ( 2019 ). http:\/\/arxiv.org\/abs\/ 1907.10874"},{"key":"e_1_3_2_1_26_1","article-title":"Should Tables Be Sorted","volume":"28","author":"Chi-Chih Yao Andrew","year":"1981","unstructured":"Andrew Chi-Chih Yao . 1981 . Should Tables Be Sorted ? J. ACM 28 , 3 ( 1981 ), 615-628. Andrew Chi-Chih Yao. 1981. Should Tables Be Sorted? J. ACM 28, 3 ( 1981 ), 615-628.","journal-title":"J. ACM"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316352"}],"event":{"name":"STOC '20: 52nd Annual ACM SIGACT Symposium on Theory of Computing","location":"Chicago IL USA","acronym":"STOC '20","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384274","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384274","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:41:12Z","timestamp":1750200072000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3357713.3384274"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":27,"alternative-id":["10.1145\/3357713.3384274","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384274","relation":{},"subject":[],"published":{"date-parts":[[2020,6,22]]},"assertion":[{"value":"2020-06-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}