Orthogonal vectors indexing
From MaRDI portal
Publication:5136259
DOI10.4230/LIPICS.ISAAC.2017.40zbMATH Open1457.68116arXiv1710.00586MaRDI QIDQ5136259FDOQ5136259
Authors: Isaac Goldstein, Ely Porat, Moshe Lewenstein 
Publication date: 25 November 2020
Full work available at URL: https://arxiv.org/abs/1710.00586
Recommendations
Analysis of algorithms and problem complexity (68Q25) Data structures (68P05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Which problems have strongly exponential complexity?
- Dictionary matching and indexing with errors and don't cares
- Lower bounds based on the exponential time hypothesis
- On the possibility of faster \textsc{SAT} algorithms
- Fast approximation algorithms for the diameter and radius of sparse graphs
- On the complexity of \(k\)-SAT
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Distance oracles beyond the Thorup-Zwick bound
- Fast set intersection and two-patterns matching
- Partial-Match Retrieval Algorithms
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Consequences of Faster Alignment of Sequences
- Finding orthogonal vectors in discrete structures
- Title not available (Why is that?)
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- More applications of the polynomial method to algorithm design
- Subtree isomorphism revisited
- Two-dimensional range diameter queries
- Faster Online Matrix-Vector Multiplication
- Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
- Conditional lower bounds for space/time tradeoffs
Cited In (7)
- Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
- Orthogonal vector measures
- Graphs cannot be indexed in polynomial time for sub-quadratic time string matching, unless SETH fails
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- An equivalence class for orthogonal vectors
- Title not available (Why is that?)
- Index Vector Elimination – Making Index Vectors Affordable
This page was built for publication: Orthogonal vectors indexing
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5136259)
