New techniques for proving fine-grained average-case hardness

DOI10.1109/FOCS46700.2020.00077MaRDI QIDQ6943978zbMATH OpenFDO

Authors M. Dalirrooyfard, Andrea Lincoln, Virginia Vassilevska Williams

Publication date 12 August 2025

Full work available at URL https://doi.org/10.1109/FOCS46700.2020.00077

Mathematics Subject Classification ID

Proceedings, conferences, collections, etc. pertaining to computer science (68-06)

Cited in

(6)

• Fine-grained complexity in a world without cryptography
• The average-case complexity of counting cliques in Erdős-Rényi hypergraphs
• Fine-grained hardness for edit distance to a fixed sequence
• (Multivariate) k-SUM as barrier to succinct computation
• The planted orthogonal vectors problem
• QSETH strikes again: finer quantum lower bounds for lattice problem, strong simulation, hitting set problem, and more

This page was built for publication: New techniques for proving fine-grained average-case hardness

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