scientific article; zbMATH DE number 7278045
From MaRDI portal
Publication:5136259
DOI10.4230/LIPICS.ISAAC.2017.40zbMath1457.68116arXiv1710.00586MaRDI QIDQ5136259
Ely Porat, Isaac Goldstein, Moshe Lewenstein
Publication date: 25 November 2020
Full work available at URL: https://arxiv.org/abs/1710.00586
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05)
Related Items (3)
Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails ⋮ Unnamed Item ⋮ Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Which problems have strongly exponential complexity?
- Conditional lower bounds for space/time tradeoffs
- Subquadratic algorithms for succinct stable matching
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Two-Dimensional Range Diameter Queries
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Known Algorithms for Edge Clique Cover are Probably Optimal
- Fast Set Intersection and Two-Patterns Matching
- Dictionary matching and indexing with errors and don't cares
- Partial-Match Retrieval Algorithms
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Subtree Isomorphism Revisited
- Faster Online Matrix-Vector Multiplication
- Consequences of Faster Alignment of Sequences
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- More Applications of the Polynomial Method to Algorithm Design
- Finding orthogonal vectors in discrete structures
- Distance Oracles beyond the Thorup--Zwick Bound
- Fast approximation algorithms for the diameter and radius of sparse graphs
- On the complexity of \(k\)-SAT
This page was built for publication:
