Circuit complexity: from the worst case to the average case.

Andreas Jakoby Rüdiger Reischuk Christian Schindelhauer

Published in: STOC (1994)

Keyphrases

average case
worst case
average case complexity
worst case analysis
upper bound
greedy algorithm
learning curves
lower bound
approximation algorithms
np hard
computational complexity
uniform distribution
online algorithms
data sets
space complexity
image processing
vc dimension
machine learning