Complexity of distributions and average-case hardness.

Dmitry Itsykson Alexander Knop Dmitry Sokolov

Published in: Electron. Colloquium Comput. Complex. (2015)

Keyphrases

average case
average case complexity
worst case
worst case analysis
lower bound
np hard
computational complexity
learning curves
uniform distribution
phase transition
sample size
upper bound
decision trees
machine learning
learning theory
vc dimension
data sets