Worst-Case to Average-Case Reductions Based on Gaussian Measures.

Daniele Micciancio Oded Regev

Published in: SIAM J. Comput. (2007)

Keyphrases

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