Complexity of Distributions and Average-Case Hardness.

Dmitry Itsykson Alexander Knop Dmitry Sokolov

Published in: ISAAC (2016)

Keyphrases

average case
average case complexity
worst case
worst case analysis
uniform distribution
upper bound
learning curves
computational complexity
lower bound
np hard
np hardness
information theoretic
sample complexity bounds
feature selection
image quality
vc dimension