New Techniques for Proving Fine-Grained Average-Case Hardness.

Mina Dalirrooyfard Andrea Lincoln Virginia Vassilevska Williams

Published in: FOCS (2020)

Keyphrases

average case
fine grained
worst case
coarse grained
worst case analysis
learning curves
np hard
upper bound
access control
uniform distribution
phase transition
tightly coupled
computational complexity
data lineage
average case complexity
sample size
text classification