The Orthogonal Vectors Conjecture for Branching Programs and Formulas
From MaRDI portal
(Redirected from Publication:5090426)
Recommendations
- An equivalence class for orthogonal vectors
- More consequences of falsifying SETH and the orthogonal vectors conjecture
- Orthogonal vectors indexing
- Faster Online Matrix-Vector Multiplication
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
Cites work
- A fast bit-parallel algorithm for computing the subset partial order
- A new algorithm for optimal 2-constraint satisfaction and its implications
- An equivalence class for orthogonal vectors
- Approximability of the discrete Fréchet distance
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Boolean function complexity. Advances and frontiers.
- Completeness for first-order properties on sparse structures with algorithmic applications
- Consequences of Faster Alignment of Sequences
- Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Finding orthogonal vectors in discrete structures
- scientific article; zbMATH DE number 1256716 (Why is no real title available?)
- scientific article; zbMATH DE number 7204473 (Why is no real title available?)
- scientific article; zbMATH DE number 3257409 (Why is no real title available?)
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- Log Space Recognition and Translation of Parenthesis Languages
- Model and objective separation with conditional lower bounds: disjunction is harder than conjunction
- More applications of the polynomial method to algorithm design
- New bounds for approximating extremal distances in undirected graphs
- On Relating Time and Space to Size and Depth
- On the complexity of k-SAT
- Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation
- Subtree isomorphism revisited
- The complexity of satisfiability of small depth circuits
- The complexity of the realization of symmetrical functions by formulae
- Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.
Cited in
(5)- Pushing the online matrix-vector conjecture off-line and identifying its easy cases
- scientific article; zbMATH DE number 5139143 (Why is no real title available?)
- Depth-3 circuit lower bounds for k-OV
- An improved algorithm for finding the shortest synchronizing words
- The planted orthogonal vectors problem
This page was built for publication: The Orthogonal Vectors Conjecture for Branching Programs and Formulas
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090426)
