ECCC-Report TR16-121https://eccc.weizmann.ac.il/report/2016/121Comments and Revisions published for TR16-121en-usFri, 23 Dec 2016 23:33:15 +0200
Revision 1
| Approximate Degree and the Complexity of Depth Three Circuits |
Mark Bun,
Justin Thaler
https://eccc.weizmann.ac.il/report/2016/121#revision1Threshold 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(\Theta(n))$. However, existing techniques are far from showing this: for all three measures, the best lower bound for depth three circuits is $\exp(\tilde{\Omega}(n^{2/5}))$. Moreover, current methods exclusively study \emph{block-composed} functions. Such methods appear intrinsically unable to prove lower bounds better than $\exp(\Omega(\sqrt{n}))$ even for depth four circuits, and have yet to prove lower bounds better than $\exp(\tilde{\Omega}(\sqrt{n}))$ 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 $\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.
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$. Fri, 23 Dec 2016 23:33:15 +0200https://eccc.weizmann.ac.il/report/2016/121#revision1
Paper TR16-121
| Approximate Degree and the Complexity of Depth Three Circuits |
Mark Bun,
Justin Thaler
https://eccc.weizmann.ac.il/report/2016/121Threshold 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(\Theta(n))$. However, existing techniques are far from showing this: for all three measures, the best lower bound for depth three circuits is $\exp(\tilde{\Omega}(n^{2/5}))$. Moreover, current methods appear intrinsically unable to prove lower bounds better than $\exp(\Omega(\sqrt{n}))$ even for depth four circuits, and have yet to prove lower bounds better than $\exp(\tilde{\Omega}(\sqrt{n}))$ 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.
Our methods 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$. The technical core of our results lies in establishing new lower bounds on the uniform approximability of depth three circuits by low-degree polynomials.Thu, 04 Aug 2016 16:55:28 +0300https://eccc.weizmann.ac.il/report/2016/121