The planted orthogonal vectors problem
From MaRDI portal
Cites work
- \(k\)-SUM in the sparse regime: complexity and applications
- A faster subquadratic algorithm for finding outlier correlations
- A new algorithm for optimal 2-constraint satisfaction and its implications
- An equivalence class for orthogonal vectors
- An illuminating algorithm for the light bulb problem
- Average-case fine-grained hardness
- Completeness for first-order properties on sparse structures with algorithmic applications
- Counting t-cliques: worst-case to average-case reductions and direct interactive proof systems
- Deterministic APSP, Orthogonal Vectors, and More
- Explicit correlation amplifiers for finding outlier correlations in deterministic subquadratic time
- Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
- Fine-grained complexity in a world without cryptography
- Fine-grained cryptanalysis: tight conditional bounds for dense \(k\)-SUM and \(k\)-XOR
- Hardness self-amplification: simplified, optimized, and unified
- Hiding cliques for cryptographic security
- Title not available (Why is no real title available?)
- Title not available (Why is no real title available?)
- More applications of the polynomial method to algorithm design
- New techniques for proving fine-grained average-case hardness
- On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
- On some fine-grained questions in algorithms and complexity
- Public-key cryptography in the fine-grained setting
- Secure communications over insecure channels
- Some estimated likelihoods for computational complexity
- The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
- The Orthogonal Vectors Conjecture for Branching Programs and Formulas
- Which problems have strongly exponential complexity?
This page was built for publication: The planted orthogonal vectors problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7322506)
