Probabilistic polynomials and Hamming nearest neighbors

DOI10.1109/FOCS.2015.18MaRDI QIDQ6946895zbMATH OpenFDO

Authors Josh Alman, Ryan Williams

Publication date 5 August 2025

Full work available at URL https://doi.org/10.1109/FOCS.2015.18

Mathematics Subject Classification ID

Theory of computing (68Qxx) Discrete mathematics in relation to computer science (68Rxx) Algorithms in computer science (68Wxx)

Cited in

(14)

• Finer-grained hardness of kernel density estimation
• Finer-grained reductions in fine-grained hardness of approximation
• Applications of random algebraic constructions to hardness of approximation
• Efficient construction of rigid matrices using an NP oracle
• Circuit depth reductions
• Approximate similarity search under edit distance using locality-sensitive hashing
• Fine-grained hardness for edit distance to a fixed sequence
• Optimal fine-grained hardness of approximation of linear equations
• Counting short vector pairs by inner product and relations to the permanent
• Fourier conjectures, correlation bounds, and majority
• Improved space-efficient approximate nearest neighbor search using function inversion
• \#SAT-algorithms for classes of threshold circuits based on probabilistic rank
• Kronecker products, low-depth circuits, and matrix rigidity
• Algorithms for the diverse-k-SAT problem: the geometry of satisfying assignments

This page was built for publication: Probabilistic polynomials and Hamming nearest neighbors

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6946895)