Fine-grained complexity of regular path queries
From MaRDI portal
Cites work
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Automata, Languages and Programming
- Boundedness of conjunctive regular path queries
- Conditional hardness for sensitivity problems
- Evaluation and enumeration problems for regular path queries
- Expressiveness and static analysis of extended conjunctive regular path queries
- Fast sparse matrix multiplication
- Finding Regular Simple Paths in Graph Databases
- Fine-Grained Complexity Theory (Tutorial)
- Hardness of Easy Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis (Invited Talk)
- scientific article; zbMATH DE number 7297854 (Why is no real title available?)
- scientific article; zbMATH DE number 7650892 (Why is no real title available?)
- scientific article; zbMATH DE number 7650987 (Why is no real title available?)
- If the current clique algorithms are optimal, so is Valiant's parser
- Matching Triangles and Basing Hardness on an Extremely Popular Conjecture
- Multiplying matrices faster than coppersmith-winograd
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules
- Popular conjectures imply strong lower bounds for dynamic problems
- Powers of tensors and fast matrix multiplication
- Querying Graphs with Data
- Regular path queries in lightweight description logics: complexity and algorithms
- Regular queries on graph databases
- Subcubic equivalences between path, matrix, and triangle problems
- The complexity of regular expressions and property paths in SPARQL
- The first-order truth behind undecidability of regular path queries determinacy
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Which regular expression patterns are hard to match?
- Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails
This page was built for publication: Fine-grained complexity of regular path queries
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7229592)
