scientific article; zbMATH DE number 7250154
From MaRDI portal
Publication:5121902
Recommendations
- On the hardness of approximate and exact (bichromatic) maximum inner product
- On the hardness of efficiently approximating maximal non-\(L\) submatrices.
- On the hardness of approximating max-satisfy
- Approximating the spectral radius of sets of matrices in the max-algebra is NP-hard
- Hardness of approximating the shortest vector problem in high \(\ell_{p}\) norms
- Hardness of bichromatic closest pair with Jaccard similarity
- Improved NP-Hardness of Approximation for Orthogonality Dimension and Minrank
- On the Hardness of Approximating Some Optimization Problems That Are Supposedly Easier Than MAX CLIQUE
- Fixed-parameter complexity and approximability of norm maximization
- On the inapproximability of maximum intersection problems
Cites work
- A (slightly) faster algorithm for klee's measure problem
- A Faster Subquadratic Algorithm for Finding Outlier Correlations
- A framework for similarity search with space-time tradeoffs using locality-sensitive filtering
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A Reliable Randomized Algorithm for the Closest-Pair Problem
- A simple randomized sieve algorithm for the closest-pair problem
- Algebrization: a new barrier in complexity theory
- Beyond locality-sensitive hashing
- Boolean function complexity. Advances and frontiers.
- Completeness for first-order properties on sparse structures with algorithmic applications
- Computational Complexity
- Conditional lower bounds for space/time tradeoffs
- Consequences of Faster Alignment of Sequences
- Edit distance cannot be computed in strongly subquadratic time (unless SETH is false)
- Efficient partition trees
- Euclidean minimum spanning trees and bichromatic closest pairs
- Even faster integer multiplication
- Exact and approximate maximum inner product search with LEMP
- Fast and deterministic constant factor approximation algorithms for LCS imply new circuit lower bounds
- Fast approximation algorithms for the diameter and radius of sparse graphs
- Faster all-pairs shortest paths via circuit complexity
- Faster integer multiplication
- Finding correlations in subquadratic time, with applications to learning parities and the closest pair problem
- Finding orthogonal vectors in discrete structures
- Higher lower bounds from the 3SUM conjecture
- scientific article; zbMATH DE number 3569833 (Why is no real title available?)
- scientific article; zbMATH DE number 1256737 (Why is no real title available?)
- scientific article; zbMATH DE number 1775389 (Why is no real title available?)
- scientific article; zbMATH DE number 1775450 (Why is no real title available?)
- Improved rectangular matrix multiplication using powers of the Coppersmith-Winograd tensor
- Matching triangles and basing hardness on an extremely popular conjecture
- More applications of the polynomial method to algorithm design
- Multivariate fine-grained complexity of longest common subsequence
- On Constructing Minimum Spanning Trees in k-Dimensional Spaces and Related Problems
- On some fine-grained questions in algorithms and complexity
- On the complexity of k-SAT
- On the difference between closest, furthest, and orthogonal pairs: nearly-linear vs barely-subquadratic complexity
- On the possibility of faster \textsc{SAT} algorithms
- Optimal data-dependent hashing for approximate near neighbors
- Probabilistic communication complexity
- Range searching with efficient hierarchical cuttings
- Rapid Multiplication of Rectangular Matrices
- The complexity of satisfiability of small depth circuits
- Towards hardness of approximation for polynomial time problems
- Towards polynomial lower bounds for dynamic problems
Cited in
(10)- On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
- Hardness of bichromatic closest pair with Jaccard similarity
- On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
- Classical algorithms from quantum and Arthur-Merlin communication protocols
- scientific article; zbMATH DE number 7561744 (Why is no real title available?)
- On the hardness of approximate and exact (bichromatic) maximum inner product
- An equivalence class for orthogonal vectors
- scientific article; zbMATH DE number 7650079 (Why is no real title available?)
- scientific article; zbMATH DE number 7650118 (Why is no real title available?)
- Finer-grained reductions in fine-grained hardness of approximation
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5121902)
