Average-case fine-grained hardness.

Marshall Ball Alon Rosen Manuel Sabin Prashant Nalini Vasudevan

Published in: STOC (2017)

Keyphrases

fine grained
average case
worst case
coarse grained
worst case analysis
learning curves
uniform distribution
access control
phase transition
computational complexity
np hard
lower bound
tightly coupled
vc dimension
upper bound
average case complexity
co occurrence