Average-case hardness of NP from exponential worst-case hardness assumptions.
Shuichi HiraharaPublished in: STOC (2021)
Keyphrases
- average case
- worst case
- double exponential
- uniform distribution
- learning dnf
- np hard
- average case complexity
- computational complexity
- worst case analysis
- upper bound
- greedy algorithm
- learning curves
- lower bound
- np complete
- sample size
- approximation algorithms
- data sets
- sample complexity bounds
- phase transition
- np hardness
- online algorithms
- machine learning