** Abstract: **

Threshold weight, margin complexity, and Majority-of-Threshold circuit size are
basic complexity measures of Boolean functions that arise in learning theory,
communication complexity, and circuit complexity. Each of these measures might
exhibit a chasm at depth three: namely, all polynomial size Boolean circuits of depth
two have polynomial complexity under the measure, but there may exist Boolean circuits
of depth three that have essentially maximal complexity exp(Omega(n)). However, existing
techniques are far from showing this: for all three measures, the best lower bound for depth three circuits is
exp(Omega(n^{2/5})) . Moreover, current methods appear intrinsically unable to prove lower bounds
better than exp(Omega(n^{1/2})) even for depth four circuits, and have yet to prove lower
bounds better than exp(Omega(n^{1/2})) for circuits of any constant depth.

We take a significant step toward showing that all of these complexity measures indeed
exhibit a chasm at depth three. Specifically, for any arbitrarily small constant delta > 0, we exhibit:

- A depth three circuit of polynomial size (in fact, an O(log n)-decision list) of complexity exp(Omega(n^{1/2-delta})) under each of these measures.
- A depth three circuit F of quasi-polynomial size (in fact, an O(log^2 n)-decision list) of complexity exp(Omega(n^{2/3-delta})) under each of these measures. The function F is also computed by a depth four circuit of polynomial size.

** Versions: **

- Mansucript [ECCC]