Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails

DOI10.1016/j.tcs.2023.114128OpenAlexW3010580865MaRDI QIDQ6076352

Alexandru I. Tomescu, Massimo Equi, Veli Mäkinen

Publication date: 21 September 2023

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2023.114128

zbMATH Keywords

lower boundsreductionsindexingorthogonal vectorscomplexity theoryFréchet distanceedit distancegraph queryexact pattern matchingsubtree isomorphism

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
• Can we compute the similarity between surfaces?
• A faster algorithm computing string edit distances
• Wheeler graphs: a framework for BWT-based data structures
• Comparison of distance measures for planar curves
• Efficient pattern matching in elastic-degenerate strings
• Indexing hypertext
• A new algorithm for optimal 2-constraint satisfaction and its implications
• Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
• Compressing and indexing labeled trees, with applications
• Indexing compressed text
• Jewels of Stringology
• New text indexing functionalities of the compressed suffix arrays
• Subtree Isomorphism Revisited
• Threesomes, Degenerates, and Love Triangles
• COMPUTING THE FRÉCHET DISTANCE BETWEEN TWO POLYGONAL CURVES
• On the Hardness and Inapproximability of Recognizing Wheeler Graphs
• Pattern matching in hypertext
• On-line pattern matching on similar texts
• ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
• Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space
• Faster Online Elastic Degenerate String Matching
• Regular Languages meet Prefix Sorting
• Indexing Variation Graphs
• Lower bounds for text indexing with mismatches and differences
• More Applications of the Polynomial Method to Algorithm Design
• Distance Oracles beyond the Thorup--Zwick Bound
• Fréchet Distance for Curves, Revisited
• Compressed Suffix Arrays and Suffix Trees with Applications to Text Indexing and String Matching
• On the complexity of \(k\)-SAT
• On the Complexity of String Matching for Graphs

This page was built for publication: Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails