{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,22]],"date-time":"2026-01-22T15:07:40Z","timestamp":1769094460876,"version":"3.49.0"},"publisher-location":"New York, NY, USA","reference-count":48,"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"}],"funder":[{"DOI":"10.13039\/100014718","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF 1715187"],"award-info":[{"award-number":["CCF 1715187"]}],"id":[{"id":"10.13039\/100014718","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Key R&D Program of China","award":["2018YFB1003202"],"award-info":[{"award-number":["2018YFB1003202"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2020,6,22]]},"DOI":"10.1145\/3357713.3384260","type":"proceedings-article","created":{"date-parts":[[2020,6,7]],"date-time":"2020-06-07T01:45:25Z","timestamp":1591494325000},"page":"1402-1415","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Lower bound for succinct range minimum query"],"prefix":"10.1145","author":[{"given":"Mingmou","family":"Liu","sequence":"first","affiliation":[{"name":"Nanjing University, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Huacheng","family":"Yu","sequence":"additional","affiliation":[{"name":"Princeton University, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2020,6,22]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"crossref","unstructured":"Andr\u00e9s Abeliuk Rodrigo C\u00e1novas and Gonzalo Navarro. 2013. Practical Compressed Sufix Trees. Algorithms 6 2 ( 2013 ) 319-351.  Andr\u00e9s Abeliuk Rodrigo C\u00e1novas and Gonzalo Navarro. 2013. Practical Compressed Sufix Trees. Algorithms 6 2 ( 2013 ) 319-351.","DOI":"10.3390\/a6020319"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(92)90003-U"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgor.2005.08.001"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222017"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/130936889"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"crossref","unstructured":"M Eug\u00e9ne Catalan. 1887. Sur les nombres de Segner. Rendiconti del Circolo Matematico di Palermo (1884-1940) 1 1 ( 1887 ) 190-201.  M Eug\u00e9ne Catalan. 1887. Sur les nombres de Segner. Rendiconti del Circolo Matematico di Palermo (1884-1940) 1 1 ( 1887 ) 190-201.","DOI":"10.1007\/BF03020089"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/080729955"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"crossref","unstructured":"Gang Chen Simon J. Puglisi and W. F. Smyth. 2008. Lempel-Ziv Factorization Using Less Time & Space. Mathematics in Computer Science 1 4 ( 01 Jun 2008 ) 605-623.  Gang Chen Simon J. Puglisi and W. F. Smyth. 2008. Lempel-Ziv Factorization Using Less Time & Space. Mathematics in Computer Science 1 4 ( 01 Jun 2008 ) 605-623.","DOI":"10.1007\/s11786-007-0024-4"},{"key":"e_1_3_2_1_9_1","volume-title":"On the range maximum-sum segment query problem. Discrete Applied Mathematics 155, 16 ( 2007 )","author":"Chen Kuan-Yu","year":"2043","unstructured":"Kuan-Yu Chen and Kun-Mao Chao . 2007. On the range maximum-sum segment query problem. Discrete Applied Mathematics 155, 16 ( 2007 ) , 2043 -2052. Kuan-Yu Chen and Kun-Mao Chao. 2007. On the range maximum-sum segment query problem. Discrete Applied Mathematics 155, 16 ( 2007 ), 2043-2052."},{"key":"e_1_3_2_1_10_1","first-page":"1089","volume-title":"New Unconditional Hardness Results for Dynamic and Online Problems. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015","author":"Cliford Rapha\u00ebl","year":"2015","unstructured":"Rapha\u00ebl Cliford , Allan Gr\u00f8nlund , and Kasper Green Larsen . 2015 . New Unconditional Hardness Results for Dynamic and Online Problems. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015 , Berkeley, CA, USA , 17-20 October, 2015. 1089 - 1107 . Rapha\u00ebl Cliford, Allan Gr\u00f8nlund, and Kasper Green Larsen. 2015. New Unconditional Hardness Results for Dynamic and Online Problems. In IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015. 1089-1107."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"crossref","unstructured":"Maxime Crochemore Costas S. Iliopoulos Marcin Kubica M. Sohel Rahman German Tischler and Tomasz Walen. 2012. Improved algorithms for the range next value problem and applications. Theor. Comput. Sci. 434 ( 2012 ) 23-34.  Maxime Crochemore Costas S. Iliopoulos Marcin Kubica M. Sohel Rahman German Tischler and Tomasz Walen. 2012. Improved algorithms for the range next value problem and applications. Theor. Comput. Sci. 434 ( 2012 ) 23-34.","DOI":"10.1016\/j.tcs.2012.02.015"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"crossref","unstructured":"Pooya Davoodi Rajeev Raman and Srinivasa Rao Satti. 2017. On Succinct Representations of Binary Trees. Mathematics in Computer Science 11 2 ( 2017 ) 177-189.  Pooya Davoodi Rajeev Raman and Srinivasa Rao Satti. 2017. On Succinct Representations of Binary Trees. Mathematics in Computer Science 11 2 ( 2017 ) 177-189.","DOI":"10.1007\/s11786-017-0294-4"},{"key":"e_1_3_2_1_13_1","first-page":"459","volume-title":"First International Symposium, ESCAPE 2007","author":"Fischer Johannes","year":"2007","unstructured":"Johannes Fischer and Volker Heun . 2007 . A New Succinct Representation of RMQInformation and Improvements in the Enhanced Sufix Array. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies , First International Symposium, ESCAPE 2007 , Hangzhou, China , April 7-9, 2007, Revised Selected Papers. 459 - 470 . Johannes Fischer and Volker Heun. 2007. A New Succinct Representation of RMQInformation and Improvements in the Enhanced Sufix Array. In Combinatorics, Algorithms, Probabilistic and Experimental Methodologies, First International Symposium, ESCAPE 2007, Hangzhou, China, April 7-9, 2007, Revised Selected Papers. 459-470."},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/090779759"},{"key":"e_1_3_2_1_15_1","volume-title":"Knowledge Discovery in Databases: PKDD","author":"Fischer Johannes","year":"2006","unstructured":"Johannes Fischer , Volker Heun , and Stefan Kramer . 2006. Optimal String Mining Under Frequency Constraints . In Knowledge Discovery in Databases: PKDD 2006 , 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22, 2006, Proceedings . 139-150. Johannes Fischer, Volker Heun, and Stefan Kramer. 2006. Optimal String Mining Under Frequency Constraints. In Knowledge Discovery in Databases: PKDD 2006, 10th European Conference on Principles and Practice of Knowledge Discovery in Databases, Berlin, Germany, September 18-22, 2006, Proceedings. 139-150."},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"crossref","unstructured":"Johannes Fischer Veli M\u00e4kinen and Gonzalo Navarro. 2009. Faster entropybounded compressed sufix trees. Theor. Comput. Sci. 410 51 ( 2009 ) 5354-5364.  Johannes Fischer Veli M\u00e4kinen and Gonzalo Navarro. 2009. Faster entropybounded compressed sufix trees. Theor. Comput. Sci. 410 51 ( 2009 ) 5354-5364.","DOI":"10.1016\/j.tcs.2009.09.012"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808675"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Anna G\u00e1l and Peter Bro Miltersen. 2007. The cell probe complexity of succinct data structures. Theor. Comput. Sci. 379 3 ( 2007 ) 405-417.  Anna G\u00e1l and Peter Bro Miltersen. 2007. The cell probe complexity of succinct data structures. Theor. Comput. Sci. 379 3 ( 2007 ) 405-417.","DOI":"10.1016\/j.tcs.2007.02.047"},{"key":"e_1_3_2_1_19_1","volume-title":"Compressed Range Minimum Queries. CoRR abs\/","author":"Gawrychowski Pawel","year":"1902","unstructured":"Pawel Gawrychowski , Seungbum Jo , Shay Mozes , and Oren Weimann . 2019. Compressed Range Minimum Queries. CoRR abs\/ 1902 .04427 ( 2019 ). Pawel Gawrychowski, Seungbum Jo, Shay Mozes, and Oren Weimann. 2019. Compressed Range Minimum Queries. CoRR abs\/ 1902.04427 ( 2019 )."},{"key":"e_1_3_2_1_20_1","first-page":"869","volume-title":"Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004","author":"Georgiadis Loukas","year":"2004","unstructured":"Loukas Georgiadis and Robert Endre Tarjan . 2004 . Finding dominators revisited: extended abstract . In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004 , New Orleans, Louisiana, USA , January 11-14, 2004. 869 - 878 . Loukas Georgiadis and Robert Endre Tarjan. 2004. Finding dominators revisited: extended abstract. In Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004. 869-878."},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973068.69"},{"key":"e_1_3_2_1_22_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016","author":"Gr\u00f8nlund Allan","year":"2016","unstructured":"Allan Gr\u00f8nlund and Kasper Green Larsen . 2016 . Towards Tight Lower Bounds for Range Reporting on the RAM. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 , July 11-15, 2016, Rome, Italy. 92 : 1-92 : 12. Allan Gr\u00f8nlund and Kasper Green Larsen. 2016. Towards Tight Lower Bounds for Range Reporting on the RAM. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. 92 : 1-92 : 12."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/0213024"},{"key":"e_1_3_2_1_24_1","volume-title":"Space-Eficient Framework for Top-k String Retrieval Problems. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009","author":"Hon Wing-Kai","year":"2009","unstructured":"Wing-Kai Hon , Rahul Shah , and Jefrey Scott Vitter . 2009 . Space-Eficient Framework for Top-k String Retrieval Problems. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009 , October 25-27, 2009, Atlanta, Georgia, USA. 713-722. Wing-Kai Hon, Rahul Shah, and Jefrey Scott Vitter. 2009. Space-Eficient Framework for Top-k String Retrieval Problems. In 50th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2009, October 25-27, 2009, Atlanta, Georgia, USA. 713-722."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2213987"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.21"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746542"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188790"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.06.052"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1577"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/545381.545469"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601073"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.68"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2010.82"},{"key":"e_1_3_2_1_36_1","volume-title":"Succincter. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008","author":"Pa\u02c7tra\u015fcu Mihai","year":"2008","unstructured":"Mihai Pa\u02c7tra\u015fcu . 2008 . Succincter. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008 , October 25-28, 2008, Philadelphia, PA, USA. 305-313. Mihai Pa\u02c7tra\u015fcu. 2008. Succincter. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA. 305-313."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.35"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132551"},{"key":"e_1_3_2_1_39_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_40_1","volume-title":"3rd Aegean Workshop on Computing, AWOC 88, Corfu, Greece, June 28-July 1, 1988, Proceedings. 33-42","author":"Ramachandran Vijaya","year":"1988","unstructured":"Vijaya Ramachandran and Uzi Vishkin . 1988 . Eficient Parallel Triconnectivity in Logarithmic Time. In VLSI Algorithms and Architectures , 3rd Aegean Workshop on Computing, AWOC 88, Corfu, Greece, June 28-July 1, 1988, Proceedings. 33-42 . Vijaya Ramachandran and Uzi Vishkin. 1988. Eficient Parallel Triconnectivity in Logarithmic Time. In VLSI Algorithms and Architectures, 3rd Aegean Workshop on Computing, AWOC 88, Corfu, Greece, June 28-July 1, 1988, Proceedings. 33-42."},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Alon Regev. 2012. A proof of Catalan's Convolution formula. Integers 12 5 ( 2012 ) 929-934.  Alon Regev. 2012. A proof of Catalan's Convolution formula. Integers 12 5 ( 2012 ) 929-934.","DOI":"10.1515\/integers-2012-0014"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Kunihiko Sadakane. 2007. Compressed Sufix Trees with Full Functionality. Theory Comput. Syst. 41 4 ( 2007 ) 589-607.  Kunihiko Sadakane. 2007. Compressed Sufix Trees with Full Functionality. Theory Comput. Syst. 41 4 ( 2007 ) 589-607.","DOI":"10.1007\/s00224-006-1198-x"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.03.011"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2008.12.006"},{"key":"e_1_3_2_1_45_1","volume-title":"Third International Workshop, WABI 2003, Budapest, Hungary, September 15-20, 2003, Proceedings. 462-475","author":"Shibuya Tetsuo","year":"2003","unstructured":"Tetsuo Shibuya and Igor Kurochkin . 2003 . Match Chaining Algorithms for cDNA Mapping. In Algorithms in Bioinformatics , Third International Workshop, WABI 2003, Budapest, Hungary, September 15-20, 2003, Proceedings. 462-475 . Tetsuo Shibuya and Igor Kurochkin. 2003. Match Chaining Algorithms for cDNA Mapping. In Algorithms in Bioinformatics, Third International Workshop, WABI 2003, Budapest, Hungary, September 15-20, 2003, Proceedings. 462-475."},{"key":"e_1_3_2_1_46_1","volume-title":"18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings. 205-215","author":"V\u00e4lim\u00e4ki Niko","year":"2007","unstructured":"Niko V\u00e4lim\u00e4ki and Veli M\u00e4kinen . 2007 . Space-Eficient Algorithms for Document Retrieval. In Combinatorial Pattern Matching , 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings. 205-215 . Niko V\u00e4lim\u00e4ki and Veli M\u00e4kinen. 2007. Space-Eficient Algorithms for Document Retrieval. In Combinatorial Pattern Matching, 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007, Proceedings. 205-215."},{"key":"e_1_3_2_1_47_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 ? Journal of the ACM (JACM) 28 , 3 ( 1981 ), 615-628. Andrew Chi-Chih Yao. 1981. Should tables be sorted ? Journal of the ACM (JACM) 28, 3 ( 1981 ), 615-628.","journal-title":"Journal of the ACM (JACM)"},{"key":"e_1_3_2_1_48_1","volume-title":"43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016","author":"Yin Yitong","year":"2016","unstructured":"Yitong Yin . 2016 . Simple Average-Case Lower Bounds for Approximate NearNeighbor from Isoperimetric Inequalities. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016 , July 11-15, 2016, Rome, Italy. 84 : 1-84 : 13. Yitong Yin. 2016. Simple Average-Case Lower Bounds for Approximate NearNeighbor from Isoperimetric Inequalities. In 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy. 84 : 1-84 : 13."},{"key":"e_1_3_2_1_49_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.3384260","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3357713.3384260","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.3384260"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,6,22]]},"references-count":48,"alternative-id":["10.1145\/3357713.3384260","10.1145\/3357713"],"URL":"https:\/\/doi.org\/10.1145\/3357713.3384260","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"}}]}}