Orthogonal vectors indexing

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

• An equivalence class for orthogonal vectors
• More consequences of falsifying SETH and the orthogonal vectors conjecture
• Conditional lower bounds for space/time tradeoffs
• Tight cell probe bounds for succinct Boolean matrix-vector multiplication
• Faster Online Matrix-Vector Multiplication

zbMATH Keywords

space complexityorthogonal vectorsSETH

Mathematics Subject Classification ID

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
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Known Algorithms for Edge Clique Cover are Probably Optimal
• 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
• Subquadratic algorithms for succinct stable matching

Cited In (5)

• 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
• 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)