Collapsing and Separating Completeness Notions under Average-Case and Worst-Case Hypotheses

Xiaoyang Gu John M. Hitchcock Aduri Pavan

Published in: CoRR (2010)

Keyphrases

average case
worst case
worst case analysis
uniform distribution
upper bound
learning curves
np hard
lower bound
approximation algorithms
greedy algorithm
computational complexity
average case complexity
semi supervised
sample size
vc dimension
online algorithms