Poly-logarithmic Frege depth lower bounds via an expander switching lemma.

Toniann Pitassi Benjamin Rossman Rocco A. Servedio Li-Yang Tan

Published in: STOC (2016)

Keyphrases

lower bound
worst case
upper bound
branch and bound
depth information
branch and bound algorithm
lower and upper bounds
depth map
johnson lindenstrauss
data sets
optimal solution
vc dimension
neural network
objective function
upper and lower bounds
concept class
online algorithms