Paper 2017/202
Average-Case Fine-Grained Hardness
Marshall Ball, Alon Rosen, Manuel Sabin, and Prashant Nalini Vasudevan
Abstract
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.
We prove our hardness results in each case by showing fine-grained reductions from solving one of three problems -- namely, Orthogonal Vectors (OV), 3SUM, and All-Pairs Shortest Paths (APSP) -- in the worst case to computing our function correctly on a uniformly random input. The conjectured hardness of OV and 3SUM then gives us functions that require
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- Published elsewhere. Minor revision. Symposium on the Theory of Computing 2017
- Keywords
- Proofs of workFine-GrainedAverage-CaseHeuristic Falsifiability
- Contact author(s)
-
msabin @ berkeley edu
marshallball @ gmail com
alon rosen @ idc ac il
prashantv91 @ gmail com - History
- 2017-03-01: received
- Short URL
- https://ia.cr/2017/202
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2017/202, author = {Marshall Ball and Alon Rosen and Manuel Sabin and Prashant Nalini Vasudevan}, title = {Average-Case Fine-Grained Hardness}, howpublished = {Cryptology {ePrint} Archive, Paper 2017/202}, year = {2017}, url = {https://eprint.iacr.org/2017/202} }