{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:29:12Z","timestamp":1750220952623,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":62,"publisher":"ACM","license":[{"start":{"date-parts":[[2019,6,23]],"date-time":"2019-06-23T00:00:00Z","timestamp":1561248000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000893","name":"Simons Foundation","doi-asserted-by":"publisher","award":["491119"],"award-info":[{"award-number":["491119"]}],"id":[{"id":"10.13039\/100000893","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1563155, CCF-1420349, CCF-1617955, CCF-1740833, CCF-1421161, CCF-1714818, CCF-1844887"],"award-info":[{"award-number":["CCF-1563155, CCF-1420349, CCF-1617955, CCF-1740833, CCF-1421161, CCF-1714818, CCF-1844887"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2019,6,23]]},"DOI":"10.1145\/3313276.3316317","type":"proceedings-article","created":{"date-parts":[[2019,6,20]],"date-time":"2019-06-20T12:19:08Z","timestamp":1561033148000},"page":"744-755","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["Local decodability of the Burrows-Wheeler transform"],"prefix":"10.1145","author":[{"given":"Sandip","family":"Sinha","sequence":"first","affiliation":[{"name":"Columbia University, USA"}]},{"given":"Omri","family":"Weinstein","sequence":"additional","affiliation":[{"name":"Columbia University, USA"}]}],"member":"320","published-online":{"date-parts":[[2019,6,23]]},"reference":[{"key":"e_1_3_2_1_1_1","unstructured":"Donald Adjeroh Timothy Bell and Amar Mukherjee. 2008.  Donald Adjeroh Timothy Bell and Amar Mukherjee. 2008."},{"volume-title":"Suffix Arrays, and Pattern Matching (1 ed.)","author":"Burrows-Wheeler Transform The","key":"e_1_3_2_1_2_1","unstructured":"The Burrows-Wheeler Transform : Data Compression , Suffix Arrays, and Pattern Matching (1 ed.) . Springer Publishing Company, Inc orporated. The Burrows-Wheeler Transform: Data Compression, Suffix Arrays, and Pattern Matching (1 ed.). Springer Publishing Company, Incorporated."},{"key":"e_1_3_2_1_3_1","volume-title":"An elementary proof of the strong converse theorem for the multiple-access channel. J. Combinatorics, Information and System Sciences","author":"Ahlswede Rudolf","year":"1982","unstructured":"Rudolf Ahlswede . 1982. An elementary proof of the strong converse theorem for the multiple-access channel. J. Combinatorics, Information and System Sciences ( 1982 ). Rudolf Ahlswede. 1982. An elementary proof of the strong converse theorem for the multiple-access channel. J. Combinatorics, Information and System Sciences (1982)."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/5684.5688"},{"key":"e_1_3_2_1_5_1","unstructured":"Philip Bille Patrick Hagge Cording Inge Li GN\u00f8rtz Benjamin Sach Hjalte Wedel VildhN\u00f8j and SN\u00f8ren Vind. {n. d.}. Fingerprints in Compressed Strings.  Philip Bille Patrick Hagge Cording Inge Li GN\u00f8rtz Benjamin Sach Hjalte Wedel VildhN\u00f8j and SN\u00f8ren Vind. {n. d.}. Fingerprints in Compressed Strings."},{"key":"e_1_3_2_1_6_1","unstructured":"Andrej Brodnik and J. Ian Munro. 1999.  Andrej Brodnik and J. Ian Munro. 1999."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795294165"},{"key":"e_1_3_2_1_8_1","unstructured":"M. Burrows and D. J. Wheeler. 1994.  M. Burrows and D. J. Wheeler. 1994."},{"volume-title":"Technical Report 124","author":"A","key":"e_1_3_2_1_9_1","unstructured":"A block-sorting lossless data compression algorithm. Technical Report 124 . Digital Equipment Corporation . A block-sorting lossless data compression algorithm. Technical Report 124. Digital Equipment Corporation."},{"key":"e_1_3_2_1_10_1","unstructured":"Yevgeniy Dodis Mihai Patrascu and Mikkel Thorup. 2010.  Yevgeniy Dodis Mihai Patrascu and Mikkel Thorup. 2010."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806771"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/DCC.2013.19"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.995542"},{"key":"e_1_3_2_1_14_1","unstructured":"Martin Farach and Mikkel Thorup. 1995.  Martin Farach and Mikkel Thorup. 1995."},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/225058.225288"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2008.12.010"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082043"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1082036.1082039"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2010.04.024"},{"key":"e_1_3_2_1_20_1","unstructured":"Travis Gagie Gonzalo Navarro and Nicola Prezza. 2018.  Travis Gagie Gonzalo Navarro and Nicola Prezza. 2018."},{"volume-title":"Text Indexing in BWT-runs Bounded Space. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201918)","key":"e_1_3_2_1_21_1","unstructured":"Optimal-time Text Indexing in BWT-runs Bounded Space. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201918) . Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1459\u20131477. http:\/\/dl.acm.org\/ citation.cfm?id=3174304.3175401 Optimal-time Text Indexing in BWT-runs Bounded Space. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201918). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1459\u20131477. http:\/\/dl.acm.org\/ citation.cfm?id=3174304.3175401"},{"key":"e_1_3_2_1_22_1","volume-title":"30th International Colloquium (ICALP","author":"G\u00e1l Anna","year":"2003","unstructured":"Anna G\u00e1l and Peter Bro Miltersen . 2003 . The Cell Probe Complexity of Succinct Data Structures. In In Automata, Languages and Programming , 30th International Colloquium (ICALP 2003. Springer-Verlag, 332\u2013344. Anna G\u00e1l and Peter Bro Miltersen. 2003. The Cell Probe Complexity of Succinct Data Structures. In In Automata, Languages and Programming, 30th International Colloquium (ICALP 2003. Springer-Verlag, 332\u2013344."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1496770.1496839"},{"volume-title":"15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings. 371\u2013382","author":"Golynski Alexander","key":"e_1_3_2_1_24_1","unstructured":"Alexander Golynski , Roberto Grossi , Ankur Gupta , Rajeev Raman , and S. Srinivasa Rao . 2007. On the Size of Succinct Indices. In Algorithms - ESA 2007 , 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings. 371\u2013382 . 3- 540- 75520- 3_34 Alexander Golynski, Roberto Grossi, Ankur Gupta, Rajeev Raman, and S. Srinivasa Rao. 2007. On the Size of Succinct Indices. In Algorithms - ESA 2007, 15th Annual European Symposium, Eilat, Israel, October 8-10, 2007, Proceedings. 371\u2013382. 3- 540- 75520- 3_34"},{"key":"e_1_3_2_1_25_1","unstructured":"Alexander Golynski Rajeev Raman and S. Srinivasa Rao. 2008.  Alexander Golynski Rajeev Raman and S. Srinivasa Rao. 2008."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69903-3_15"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2007.07.020"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/2394373.2394390"},{"key":"e_1_3_2_1_29_1","unstructured":"S. Rao Kosaraju and Giovanni Manzini. 1999.  S. Rao Kosaraju and Giovanni Manzini. 1999."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797331105"},{"key":"e_1_3_2_1_31_1","volume-title":"Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201990)","author":"Manber Udi","year":"1990","unstructured":"Udi Manber and Gene Myers . 1990 . Suffix Arrays: A New Method for On-line String Searches . In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201990) . Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 319\u2013327. http:\/\/dl.acm.org\/citation.cfm?id=3 20176. Udi Manber and Gene Myers. 1990. Suffix Arrays: A New Method for On-line String Searches. In Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201990). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 319\u2013327. http:\/\/dl.acm.org\/citation.cfm?id=320176."},{"key":"e_1_3_2_1_32_1","unstructured":"320218  320218"},{"key":"e_1_3_2_1_33_1","unstructured":"Giovanni Manzini. 2001.  Giovanni Manzini. 2001."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/382780.382782"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-004-1094-1"},{"key":"e_1_3_2_1_36_1","unstructured":"Edward M. McCreight. 1976.  Edward M. McCreight. 1976."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/321941.321946"},{"key":"e_1_3_2_1_38_1","unstructured":"321946  321946"},{"key":"e_1_3_2_1_39_1","unstructured":"Peter Bro Miltersen. 2005.  Peter Bro Miltersen. 2005."},{"volume-title":"Bounds on the Size of Selection and Rank Indexes. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201905)","author":"Lower","key":"e_1_3_2_1_40_1","unstructured":"Lower Bounds on the Size of Selection and Rank Indexes. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201905) . Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 11\u201312. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070435 Lower Bounds on the Size of Selection and Rank Indexes. In Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms (SODA \u201905). Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 11\u201312. http:\/\/dl.acm.org\/citation.cfm?id=1070432.1070435"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"crossref","unstructured":"Alistair Moffat. 1990. Implementing the PPM Data Compression Scheme.  Alistair Moffat. 1990. Implementing the PPM Data Compression Scheme.","DOI":"10.1109\/26.61469"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2012.03.005"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/1216370.1216372"},{"key":"e_1_3_2_1_44_1","unstructured":"1216372  1216372"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369909"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.83"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132551"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873612"},{"key":"e_1_3_2_1_49_1","unstructured":"1873612  1873612"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109693"},{"key":"e_1_3_2_1_51_1","unstructured":"Julian Seward. {n. d.}. Bzip2. www.bzip.org  Julian Seward. {n. d.}. Bzip2. www.bzip.org"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btq217"},{"key":"e_1_3_2_1_53_1","unstructured":"Sandip Sinha and Omri Weinstein. 2018.  Sandip Sinha and Omri Weinstein. 2018."},{"key":"e_1_3_2_1_54_1","volume-title":"arXiv","author":"Burrows-Wheeler Transform Local Decodability","year":"1808","unstructured":"Local Decodability of the Burrows-Wheeler Transform . arXiv : 1808 .03978 Local Decodability of the Burrows-Wheeler Transform. arXiv: 1808.03978"},{"key":"e_1_3_2_1_55_1","unstructured":"Emanuele Viola. 2009.  Emanuele Viola. 2009."},{"key":"e_1_3_2_1_56_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC) 16","author":"Lower Cell-Probe","year":"2009","unstructured":"Cell-Probe Lower Bounds for Prefix Sums . Electronic Colloquium on Computational Complexity (ECCC) 16 ( 2009 ), 54. http:\/\/eccc. hpiweb.de\/report\/2009\/054 Cell-Probe Lower Bounds for Prefix Sums. Electronic Colloquium on Computational Complexity (ECCC) 16 (2009), 54. http:\/\/eccc. hpiweb.de\/report\/2009\/054"},{"key":"e_1_3_2_1_57_1","unstructured":"Emanuele Viola. 2012.  Emanuele Viola. 2012."},{"key":"e_1_3_2_1_58_1","volume-title":"1593\u20131604","author":"Lower Bit-Probe","year":"2012","unstructured":"Bit-Probe Lower Bounds for Succinct Data Structures . SIAM J. Comput . 41, 6 ( 2012 ), 1593\u20131604 . Bit-Probe Lower Bounds for Succinct Data Structures. SIAM J. Comput. 41, 6 (2012), 1593\u20131604."},{"key":"e_1_3_2_1_59_1","unstructured":"Emanuele Viola. 2017.  Emanuele Viola. 2017."},{"key":"e_1_3_2_1_60_1","volume-title":"Electronic Colloquium on Computational Complexity (ECCC) 24","author":"A","year":"2017","unstructured":"A sampling lower bound for permutations. Electronic Colloquium on Computational Complexity (ECCC) 24 ( 2017 ), 166. https:\/\/eccc. weizmann.ac.il\/report\/2017\/166 A sampling lower bound for permutations. Electronic Colloquium on Computational Complexity (ECCC) 24 (2017), 166. https:\/\/eccc. weizmann.ac.il\/report\/2017\/166"},{"key":"e_1_3_2_1_61_1","first-page":"60","article-title":"Sampling lower bounds: boolean average-case and permutations","volume":"25","author":"Viola Emanuele","year":"2018","unstructured":"Emanuele Viola . 2018 . Sampling lower bounds: boolean average-case and permutations . Electronic Colloquium on Computational Complexity (ECCC) 25 (2018), 60 . https:\/\/eccc.weizmann.ac.il\/report\/2018\/060 Emanuele Viola. 2018. Sampling lower bounds: boolean average-case and permutations. Electronic Colloquium on Computational Complexity (ECCC) 25 (2018), 60. https:\/\/eccc.weizmann.ac.il\/report\/2018\/060","journal-title":"Electronic Colloquium on Computational Complexity (ECCC)"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1978.1055934"}],"event":{"name":"STOC '19: 51st Annual ACM SIGACT Symposium on the Theory of Computing","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Phoenix AZ USA","acronym":"STOC '19"},"container-title":["Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316317","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316317","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3313276.3316317","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T23:54:01Z","timestamp":1750204441000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3313276.3316317"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,6,23]]},"references-count":62,"alternative-id":["10.1145\/3313276.3316317","10.1145\/3313276"],"URL":"https:\/\/doi.org\/10.1145\/3313276.3316317","relation":{},"subject":[],"published":{"date-parts":[[2019,6,23]]},"assertion":[{"value":"2019-06-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}