An Improved Worst-Case to Average-Case Connection for Lattice Problems.

Jin-yi Cai Ajay Nerurkar

Published in: FOCS (1997)

Keyphrases

average case
worst case
average case complexity
uniform distribution
worst case analysis
learning curves
lower bound
computational complexity
upper bound
decision problems
online algorithms
machine learning
high dimensional
greedy algorithm
approximation algorithms