Worst case to Average case reductions for polynomials.

Shachar Lovett Tali Kaufman

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

Keyphrases

average case
worst case
worst case analysis
learning curves
uniform distribution
upper bound
greedy algorithm
approximation algorithms
lower bound
np hard
average case complexity
vc dimension