Average-case fine-grained hardness

We present functions that can be computed in some fixed polynomial time but are hard on average for any algorithm that runs in slightly smaller time, assuming widely-conjectured worst-case hardness for problems from the study of fine-grained complexity. Unconditional constructions of such functions are known from before (Goldmann et al., IPL '94), but these have been canonical functions that have not found further use, while our functions are closely related to well-studied problems and have considerable algebraic structure.

Authors

• Marshall Ball
• Alon Rosen
• Manuel Sabin
• Prashant Nalini Vasudevan

Keywords

• Average-Case Complexity
• Cryptography
• Fine-Grained Complexity
• Heuristic Falsifiability
• Proofs of Work
• Worst-Case to Average-Case Reduction