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 \emph{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 exclusively study block-composed functions. Such 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(\tilde{Omega}(n^{1/2})) for circuits of any constant depth.

We take a step toward showing that all of these complexity measures indeed exhibit a chasm at depth three. Specifically, for any arbitrarily small constant 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.

Our methods go beyond the block-composed functions studied in prior work, and hence may not be subject to the same barriers. In particular, we suggest natural candidate functions that may exhibit stronger bounds, of the form exp(\tilde{Omega}(n)), where the \tilde{Omega} notation hides factors polylogarithmic in n.

Versions: