Approximate Degree and the Complexity of Depth Three Circuits

M. Bun and J. Thaler

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:

Our methods suggest natural candidate functions that may exhibit stronger bounds, of the form exp(\tilde{Theta}(n)), where the \tilde{Theta} notation hides factors polylogarithmic in n. The technical core of our results lies in establishing new lower bounds on the uniform approximability of depth three circuits by low-degree polynomials.

Versions: