An Average-Case Depth Hierarchy Theorem for Boolean Circuits.

Johan Håstad Benjamin Rossman Rocco A. Servedio Li-Yang Tan

Published in: J. ACM (2017)

Keyphrases

average case
uniform distribution
worst case
boolean functions
worst case analysis
learning curves
real valued
average case complexity
online algorithms
sample complexity bounds
data sets
decision trees
special case
upper bound