The Orthogonal Vectors Conjecture for Branching Programs and Formulas
From MaRDI portal
Publication:5090426
DOI10.4230/LIPIcs.ITCS.2019.48OpenAlexW2963561377MaRDI QIDQ5090426
Daniel M. Kane, R. Ryan Williams
Publication date: 18 July 2022
Full work available at URL: https://arxiv.org/abs/1709.05294
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Boolean function complexity. Advances and frontiers.
- The complexity of the realization of symmetrical functions by formulae
- A fast bit-parallel algorithm for computing the subset partial order
- A new algorithm for optimal 2-constraint satisfaction and its implications
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- Approximability of the discrete Fréchet distance
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- The Complexity of Satisfiability of Small Depth Circuits
- On Relating Time and Space to Size and Depth
- Log Space Recognition and Translation of Parenthesis Languages
- New Bounds for Approximating Extremal Distances in Undirected Graphs
- Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
- Deterministic APSP, Orthogonal Vectors, and More: Quickly Derandomizing Razborov-Smolensky
- Subtree Isomorphism Revisited
- Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications
- Model and Objective Separation with Conditional Lower Bounds
- Consequences of Faster Alignment of Sequences
- An Equivalence Class for Orthogonal Vectors
- More Applications of the Polynomial Method to Algorithm Design
- Truly Subquadratic-Time Extension Queries and Periodicity Detection in Strings with Uncertainties.
- Finding orthogonal vectors in discrete structures
- Fast approximation algorithms for the diameter and radius of sparse graphs
- On the complexity of \(k\)-SAT
This page was built for publication: The Orthogonal Vectors Conjecture for Branching Programs and Formulas
