{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T04:52:51Z","timestamp":1776055971922,"version":"3.50.1"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T00:00:00Z","timestamp":1776038400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T00:00:00Z","timestamp":1776038400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"funder":[{"name":"NSF","award":["CCF-20-08551"],"award-info":[{"award-number":["CCF-20-08551"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2026,6]]},"DOI":"10.1007\/s00453-026-01385-5","type":"journal-article","created":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T04:28:34Z","timestamp":1776054514000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["A General Technique for Searching in Implicit Sets via Function Inversion"],"prefix":"10.1007","volume":"88","author":[{"given":"Boris","family":"Aronov","sequence":"first","affiliation":[]},{"given":"Jean","family":"Cardinal","sequence":"additional","affiliation":[]},{"given":"Justin","family":"Dallant","sequence":"additional","affiliation":[]},{"given":"John","family":"Iacono","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,4,13]]},"reference":[{"issue":"5","key":"1385_CR1","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1007\/BF01187037","volume":"9","author":"PK Agarwal","year":"1993","unstructured":"Agarwal, P.K., Aronov, B., Sharir, M., Suri, S.: Selecting distances in the plane. Algorithmica 9(5), 495\u2013514 (1993)","journal-title":"Algorithmica"},{"key":"1385_CR2","doi-asserted-by":"crossref","unstructured":"Aronov, B., Cardinal, J., Dallant, J., Iacono, J.: A general technique for searching in implicit sets via function inversion. In 2024 Symposium on Simplicity in Algorithms, SOSA 2024, Alexandria, VA, USA, January 8-10, (2024 ) Parter, M., Pettie, S. Eds., SIAM, pp.\u00a0215\u2013223 (2024)","DOI":"10.1137\/1.9781611977936.20"},{"key":"1385_CR3","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2022.101963","volume":"110","author":"B Aronov","year":"2023","unstructured":"Aronov, B., Ezra, E., Sharir, M., Zigdon, G.: Time and space efficient collinearity indexing. Comput. Geom. 110, 101963 (2023)","journal-title":"Comput. Geom."},{"issue":"4","key":"1385_CR4","doi-asserted-by":"publisher","first-page":"698","DOI":"10.1007\/s00454-018-0040-y","volume":"61","author":"L Barba","year":"2019","unstructured":"Barba, L., Cardinal, J., Iacono, J., Langerman, S., Ooms, A., Solomon, N.: Subquadratic algorithms for algebraic 3SUM. Discret. Comput. Geom. 61(4), 698\u2013734 (2019)","journal-title":"Discret. Comput. Geom."},{"issue":"3","key":"1385_CR5","doi-asserted-by":"publisher","first-page":"333","DOI":"10.1016\/j.jda.2003.12.001","volume":"2","author":"S Bespamyatnikh","year":"2004","unstructured":"Bespamyatnikh, S., Segal, M.: Selecting distances in arrangements of hyperplanes spanned by points. J. Discrete Algorithms 2(3), 333\u2013345 (2004)","journal-title":"J. Discrete Algorithms"},{"key":"1385_CR6","unstructured":"Bille, P., G\u00f8rtz, I.\u00a0L., Lewenstein, M., Pissis, S.\u00a0P., Rotenberg, E., Steiner, T.\u00a0A.: Gapped string indexing in subquadratic space and sublinear query time. In 41st International Symposium on Theoretical Aspects of Computer Science, STACS 2024, March 12-14, (2024), Clermont-Ferrand, France Beyersdorff, O., Kant\u00e9, M.\u00a0M., Kupferman, O., Lokshtanov, D. Eds., vol.\u00a0289 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp.\u00a016:1\u201316:21 (2024)"},{"issue":"1","key":"1385_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/S0925-7721(97)00025-4","volume":"10","author":"H Br\u00f6nnimann","year":"1998","unstructured":"Br\u00f6nnimann, H., Chazelle, B.: Optimal slope selection via cuttings. Comput. Geom. 10(1), 23\u201329 (1998)","journal-title":"Comput. Geom."},{"issue":"1","key":"1385_CR8","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s004530010005","volume":"27","author":"C Burnikel","year":"2000","unstructured":"Burnikel, C., Fleischer, R., Mehlhorn, K., Schirra, S.: A strong and easily computable separation bound for arithmetic expressions involving radicals. Algorithmica 27(1), 87\u201399 (2000)","journal-title":"Algorithmica"},{"key":"1385_CR9","unstructured":"Cardinal, J., Sharir, M.: Improved algebraic degeneracy testing. In 39th International Symposium on Computational Geometry, SoCG 2023, June 12\u201315, (2023), Dallas, Texas, USA Chambers, E.\u00a0W., Gudmundsson, J. Eds., vol.\u00a0258 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp.\u00a022:1\u201322:16 (2023)"},{"issue":"5","key":"1385_CR10","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1007\/BF00263295","volume":"24","author":"B Chazelle","year":"1987","unstructured":"Chazelle, B.: Some techniques for geometric searching with implicit set representations. Acta Informatica 24(5), 565\u2013582 (1987)","journal-title":"Acta Informatica"},{"issue":"4","key":"1385_CR11","doi-asserted-by":"publisher","first-page":"792","DOI":"10.1137\/0218055","volume":"18","author":"R Cole","year":"1989","unstructured":"Cole, R., Salowe, J.S., Steiger, W.L., Szemer\u00e9di, E.: An optimal-time algorithm for slope selection. SIAM J. Comput. 18(4), 792\u2013810 (1989)","journal-title":"SIAM J. Comput."},{"key":"1385_CR12","doi-asserted-by":"crossref","unstructured":"Corrigan-Gibbs, H., Kogan, D.: The function-inversion problem: Barriers and opportunities. In Theory of Cryptography - 17th International Conference, TCC 2019, Nuremberg, Germany, December 1\u20135, 2019, Proceedings, Part I Hofheinz, D., Rosen, A. Eds., vol.\u00a011891 of Lecture Notes in Computer Science, Springer, pp.\u00a0393\u2013421 (2019)","DOI":"10.1007\/978-3-030-36030-6_16"},{"key":"1385_CR13","doi-asserted-by":"crossref","unstructured":"De, A., Trevisan, L., Tulsiani, M.: Time space tradeoffs for attacks against one-way functions and prgs. In Advances in Cryptology - CRYPTO 2010, 30th Annual Cryptology Conference, Santa Barbara, CA, USA, August 15-19, (2010). Proceedings Rabin,T. Ed., vol.\u00a06223 of Lecture Notes in Computer Science, Springer, pp.\u00a0649\u2013665 (2010)","DOI":"10.1007\/978-3-642-14623-7_35"},{"key":"1385_CR14","unstructured":"Dvo\u0159\u00e1k, P., Kouck\u00fd, M., Kr\u00e1l, K., Sl\u00edvov\u00e1, V.: Data structures lower bounds and popular conjectures. In 29th Annual European Symposium on Algorithms, ESA 2021, September 6-8, (2021), Lisbon, Portugal (Virtual Conference) Mutzel, P., Pagh, R., Herman, G. Eds., vol.\u00a0204 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp.\u00a039:1\u201339:15 (2021)"},{"key":"1385_CR15","doi-asserted-by":"crossref","unstructured":"Farach, M.: Optimal suffix tree construction with large alphabets. In 38th Annual Symposium on Foundations of Computer Science, FOCS \u201997, Miami Beach, Florida, USA, October 19\u201322, 1997 IEEE Computer Society, pp.\u00a0137\u2013143 (1997)","DOI":"10.1109\/SFCS.1997.646102"},{"issue":"6","key":"1385_CR16","doi-asserted-by":"publisher","first-page":"987","DOI":"10.1145\/355541.355547","volume":"47","author":"M Farach-Colton","year":"2000","unstructured":"Farach-Colton, M., Ferragina, P., Muthukrishnan, S.: On the sorting-complexity of suffix tree construction. J. ACM 47(6), 987\u20131011 (2000)","journal-title":"J. ACM"},{"issue":"3","key":"1385_CR17","doi-asserted-by":"publisher","first-page":"790","DOI":"10.1137\/S0097539795280512","volume":"29","author":"A Fiat","year":"1999","unstructured":"Fiat, A., Naor, M.: Rigorous time\/space trade-offs for inverting functions. SIAM J. Comput. 29(3), 790\u2013803 (1999)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1385_CR18","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1016\/j.comgeo.2011.11.006","volume":"45","author":"A Gajentaan","year":"2012","unstructured":"Gajentaan, A., Overmars, M.H.: On a class of $${O}(n^2)$$ problems in computational geometry. Comput. Geom. 45(4), 140\u2013152 (2012)","journal-title":"Comput. Geom."},{"key":"1385_CR19","doi-asserted-by":"crossref","unstructured":"Gennaro, R., Trevisan, L.: Lower bounds on the efficiency of generic cryptographic constructions. In 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA IEEE Computer Society, pp.\u00a0305\u2013313 (2000)","DOI":"10.1109\/SFCS.2000.892119"},{"key":"1385_CR20","doi-asserted-by":"crossref","unstructured":"Goldstein, I., Kopelowitz, T., Lewenstein, M., Porat, E.: Conditional lower bounds for space\/time tradeoffs. In Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John\u2019s, NL, Canada, July 31 \u2013 August 2, 2017, Proceedings Ellen, F., Kolokolova, A., Sack, J. Eds., vol.\u00a010389 of Lecture Notes in Computer Science, Springer, pp.\u00a0421\u2013436 (2017)","DOI":"10.1007\/978-3-319-62127-2_36"},{"key":"1385_CR21","doi-asserted-by":"crossref","unstructured":"Golovnev, A., Guo, S., Horel, T., Park, S., Vaikuntanathan, V.: Data structures meet cryptography: 3SUM with preprocessing. In Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22\u201326, (2020) Makarychev, K., Makarychev, Y., Tulsiani, M., Kamath, G., Chuzhoy, J. Eds., ACM, pp.\u00a0294\u2013307 (2020)","DOI":"10.1145\/3357713.3384342"},{"key":"1385_CR22","doi-asserted-by":"crossref","unstructured":"Golovnev, A., Guo, S., Peters, S., Stephens-Davidowitz, N.: Revisiting time-space tradeoffs for function inversion. In Advances in Cryptology - CRYPTO 2023 - 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20-24, 2023, Proceedings, Part II Handschuh, H., Lysyanskaya, A. Eds., vol.\u00a014082 of Lecture Notes in Computer Science, Springer, pp.\u00a0453\u2013481 (2023)","DOI":"10.1007\/978-3-031-38545-2_15"},{"key":"1385_CR23","doi-asserted-by":"crossref","unstructured":"Goodrich, M.\u00a0T.: Geometric partitioning made easier, even in parallel. In Proceedings of the Ninth Annual Symposium on Computational GeometrySan Diego, CA, USA, May 19-21, 1993, C.\u00a0Yap, Ed., ACM, pp.\u00a073\u201382 (1993)","DOI":"10.1145\/160985.161002"},{"key":"1385_CR24","doi-asserted-by":"crossref","unstructured":"Gr\u00f8nlund, A., Pettie, S.: Threesomes, degenerates, and love triangles. J. ACM 65, 4 22:1\u201322:25 (2018)","DOI":"10.1145\/3185378"},{"key":"1385_CR25","doi-asserted-by":"crossref","unstructured":"Hirahara, S., Ilango, R., Williams, R.\u00a0R.: Beating brute force for compression problems. In Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, June 24-28 (2024), Mohar, B., Shinkar, I., O\u2019Donnell, R. Eds., ACM, pp.\u00a0659\u2013670 (2024)","DOI":"10.1145\/3618260.3649778"},{"key":"1385_CR26","unstructured":"Iacono, J., Langerman, S.: Dynamic point location in fat hyperrectangles with integer coordinates. In Proceedings of the 12th Canadian Conference on Computational Geometry, Fredericton, New Brunswick, Canada, August 16-19 (2000)"},{"key":"1385_CR27","doi-asserted-by":"crossref","unstructured":"Kane, D.\u00a0M., Lovett, S., Moran, S.: Near-optimal linear decision trees for k-SUM and related problems. J. ACM 66, 3 16:1\u201316:18 (2019)","DOI":"10.1145\/3285953"},{"issue":"3","key":"1385_CR28","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/0020-0190(93)90234-Z","volume":"47","author":"MJ Katz","year":"1993","unstructured":"Katz, M.J., Sharir, M.: Optimal slope selection via expanders. Inf. Process. Lett. 47(3), 115\u2013122 (1993)","journal-title":"Inf. Process. Lett."},{"issue":"5","key":"1385_CR29","doi-asserted-by":"publisher","first-page":"1384","DOI":"10.1137\/S0097539794268649","volume":"26","author":"MJ Katz","year":"1997","unstructured":"Katz, M.J., Sharir, M.: An expander-based approach to geometric optimization. SIAM J. Comput. 26(5), 1384\u20131408 (1997)","journal-title":"SIAM J. Comput."},{"issue":"2\u20134","key":"1385_CR30","doi-asserted-by":"publisher","first-page":"126","DOI":"10.1016\/j.jda.2004.08.019","volume":"3","author":"DK Kim","year":"2005","unstructured":"Kim, D.K., Sim, J.S., Park, H., Park, K.: Constructing suffix arrays in linear time. J. Discrete Algorithms 3(2\u20134), 126\u2013142 (2005)","journal-title":"J. Discrete Algorithms"},{"issue":"2\u20134","key":"1385_CR31","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1016\/j.jda.2004.08.002","volume":"3","author":"P Ko","year":"2005","unstructured":"Ko, P., Aluru, S.: Space efficient linear time construction of suffix arrays. J. Discrete Algorithms 3(2\u20134), 143\u2013156 (2005)","journal-title":"J. Discrete Algorithms"},{"key":"1385_CR32","unstructured":"Kopelowitz, T., Porat, E.: The strong 3SUM-INDEXING conjecture is false. Manuscript (2019)"},{"issue":"5","key":"1385_CR33","doi-asserted-by":"publisher","first-page":"935","DOI":"10.1137\/0222058","volume":"22","author":"U Manber","year":"1993","unstructured":"Manber, U., Myers, E.W.: Suffix arrays: A new method for on-line string searches. SIAM J. Comput. 22(5), 935\u2013948 (1993)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"1385_CR34","doi-asserted-by":"publisher","first-page":"183","DOI":"10.1016\/0020-0190(91)90177-J","volume":"39","author":"J Matousek","year":"1991","unstructured":"Matousek, J.: Randomized optimal algorithm for slope selection. Inf. Process. Lett. 39(4), 183\u2013187 (1991)","journal-title":"Inf. Process. Lett."},{"key":"1385_CR35","unstructured":"Mazor, N., Pass, R.: The non-uniform perebor conjecture for time-bounded kolmogorov complexity is false. In 15th Innovations in Theoretical Computer Science Conference, ITCS 2024, January 30 to February 2, 2024, Berkeley, CA, USA Guruswami, V. Ed., vol.\u00a0287 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, pp.\u00a080:1\u201380:20 (2024)"},{"key":"1385_CR36","unstructured":"McCauley, S.: Improved space-efficient approximate nearest neighbor search using function inversion. To appear at ESA\u201924 (2024)"},{"issue":"2","key":"1385_CR37","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1016\/0020-0190(83)90075-3","volume":"17","author":"DE Willard","year":"1983","unstructured":"Willard, D.E.: Log-logarithmic worst-case range queries are possible in space $$\\theta (n)$$. Inf. Process. Lett. 17(2), 81\u201384 (1983)","journal-title":"Inf. Process. Lett."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01385-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-026-01385-5","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-026-01385-5.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,13]],"date-time":"2026-04-13T04:28:45Z","timestamp":1776054525000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-026-01385-5"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,4,13]]},"references-count":37,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2026,6]]}},"alternative-id":["1385"],"URL":"https:\/\/doi.org\/10.1007\/s00453-026-01385-5","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,4,13]]},"assertion":[{"value":"4 April 2025","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"30 March 2026","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 April 2026","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"37"}}