On Worst-Case to Average-Case Reductions for NP Problems.

Andrej Bogdanov Luca Trevisan

Published in: SIAM J. Comput. (2006)

Keyphrases

average case
worst case
worst case analysis
average case complexity
np complete
learning curves
uniform distribution
np hard
upper bound
greedy algorithm
linear programming
learning algorithm
special case
semi supervised
sample size
vc dimension