Finer-grained reductions in fine-grained hardness of approximation

DOI10.1016/J.TCS.2024.114976MaRDI QIDQ6658294zbMATH OpenFDO

Authors Elie Abboud, Noga Ron-Zewi

Publication date 8 January 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2024.114976

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On closest pair in Euclidean metric: monochromatic is as hard as bichromatic
• On Closest Pair in Euclidean Metric: Monochromatic is as Hard as Bichromatic
• Hardness of approximate nearest neighbor search
• Fine-grained complexity meets \(\mathrm{IP} = \mathrm{PSPACE}\)
• scientific article; zbMATH DE number 7250154

Cites work

• A low-complexity algorithm for the construction of algebraic-geometric codes better than the Gilbert-Varshamov bound
• A new algorithm for optimal 2-constraint satisfaction and its implications
• A simple randomized sieve algorithm for the closest-pair problem
• Algebraic methods for interactive proof systems
• Algebrization: a new barrier in complexity theory
• An equivalence class for orthogonal vectors
• Completeness for first-order properties on sparse structures with algorithmic applications
• Deterministic APSP, Orthogonal Vectors, and More
• Graph-Theoretical Methods for Detecting and Describing Gestalt Clusters
• Hardness of approximate nearest neighbor search
• scientific article; zbMATH DE number 6680986 (Why is no real title available?)
• scientific article; zbMATH DE number 3597592 (Why is no real title available?)
• scientific article; zbMATH DE number 6317138 (Why is no real title available?)
• More applications of the polynomial method to algorithm design
• On the complexity of k-SAT
• On the hardness of approximate and exact (bichromatic) maximum inner product
• Subcubic equivalences between path, matrix, and triangle problems

This page was built for publication: Finer-grained reductions in fine-grained hardness of approximation

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