Worst-Case to Average-Case Reductions Revisited.

Dan Gutfreund Amnon Ta-Shma

Published in: APPROX-RANDOM (2007)

Keyphrases

average case
worst case
worst case analysis
learning curves
uniform distribution
greedy algorithm
upper bound
approximation algorithms
computational complexity
lower bound
np hard
online algorithms
learning algorithm
pairwise
boolean functions
average case complexity