Malign Distributions for Average Case Circuit Complexity.

Andreas Jakoby Rüdiger Reischuk Christian Schindelhauer

Published in: STACS (1995)

Keyphrases

average case
average case complexity
worst case
worst case analysis
uniform distribution
learning curves
lower bound
computational complexity
vc dimension
machine learning
np hard
decision problems
sample complexity bounds