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

Published in: APPROX-RANDOM (2010)

Keyphrases

average case
worst case
np hard
computational complexity
worst case analysis
uniform distribution
learning curves
lower bound
upper bound
greedy algorithm
average case complexity
approximation algorithms
special case
sample complexity bounds
small number
online algorithms