Relativized Worlds Without Worst-Case to Average-Case Reductions for NP.

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

Keyphrases

average case
worst case
np hard
computational complexity
worst case analysis
learning curves
uniform distribution
upper bound
lower bound
average case complexity
greedy algorithm
vector space
sample size
vc dimension
machine learning
high dimensional
feature selection