{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:28Z","timestamp":1781031448180,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":23,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2103813"],"award-info":[{"award-number":["CCF-2103813"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"National Science Foundation","award":["CAREER-2045641"],"award-info":[{"award-number":["CAREER-2045641"]}]},{"name":"National Science Foundation","award":["CNS-232595"],"award-info":[{"award-number":["CNS-232595"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800818","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1061-1072","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Space-Efficient Text Indexing with Mismatches using Function Inversion"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-5063-0700","authenticated-orcid":false,"given":"Jackson","family":"Bibbens","sequence":"first","affiliation":[{"name":"University of Massachusetts at Amherst, Amherst, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0008-1725-6316","authenticated-orcid":false,"given":"Levi","family":"Borevitz","sequence":"additional","affiliation":[{"name":"Northwestern University, Evanston, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8196-9662","authenticated-orcid":false,"given":"Samuel","family":"McCauley","sequence":"additional","affiliation":[{"name":"Williams College, Williamstown, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2261250.2261301"},{"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","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977936.20"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2022.101963"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-19929-0_6"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.STACS.2024.16"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2011.04.004"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-60044-2_33"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.70"},{"key":"e_1_3_2_1_10_1","volume-title":"Proc. 36th Annual ACM Symposium on Theory of Computing (STOC). ACM","author":"Cole Richard","year":"2004","unstructured":"Richard Cole, Lee-Ad Gottlieb, and Moshe Lewenstein. 2004. Dictionary matching and indexing with errors and don\u2019t cares. In Proc. 36th Annual ACM Symposium on Theory of Computing (STOC). ACM, New York, NY USA. 91\u2013100."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-36030-6_16"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795280512"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384342"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1980.1056220"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.11.022"},{"key":"e_1_3_2_1_16_1","unstructured":"Yael Kirkpatrick John Kuszmaul Surya Mathialagan and Virginia Vassilevska Williams. 2026. Preprocessed 3SUM for Unknown Universes with Subquadratic Space. arxiv:2602.11363"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978971.68"},{"key":"e_1_3_2_1_18_1","unstructured":"Tsvi Kopelowitz and Ely Porat. 2019. The strong 3SUM-INDEXING conjecture is false. arxiv:1907.11206"},{"key":"e_1_3_2_1_19_1","volume-title":"Proc. 35th Annual Symposium on Combinatorial Pattern Matching (CPM). 296","author":"Kosolobov Dmitry","year":"2024","unstructured":"Dmitry Kosolobov and Nikita Sivukhin. 2024. Construction of Sparse Suffix Trees and LCE Indexes in Optimal Time and Space. In Proc. 35th Annual Symposium on Combinatorial Pattern Matching (CPM). 296, Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. 20:1\u201320:18."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/3118740.3118870"},{"key":"e_1_3_2_1_21_1","volume-title":"Proc. 32nd European Symposium on Algorithms (ESA) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"19","author":"McCauley Samuel","year":"2024","unstructured":"Samuel McCauley. 2024. Improved Space-Efficient Approximate Nearest Neighbor Search Using Function Inversion. In Proc. 32nd European Symposium on Algorithms (ESA) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 308). Schloss Dagstuhl \u2013 Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany. 88:1\u201388:19."},{"key":"e_1_3_2_1_22_1","volume-title":"Papert","author":"Minsky Marvin","year":"1969","unstructured":"Marvin Minsky and Seymour A. Papert. 1969. Perceptrons. MIT Press, Cambridge, MA USA."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2016.10.003"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800818","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800818","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:02:42Z","timestamp":1781028162000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800818"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":23,"alternative-id":["10.1145\/3798129.3800818","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800818","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}