ECCC-Report TR11-125https://eccc.weizmann.ac.il/report/2011/125Comments and Revisions published for TR11-125en-usFri, 18 May 2012 07:49:29 +0300
Revision 1
| Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators |
Andrew Drucker
https://eccc.weizmann.ac.il/report/2011/125#revision1We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show sharp limitations of several existing lower-bound methods for this model.
First, we study an information-theoretic lower-bound method due to Cherukhin, that yields bounds of form $\Omega_d(n \cdot \lambda_{d - 1}(n))$ on the number of wires needed to compute cyclic convolutions in depth $d \geq 2$. This was the first improvement over the lower bounds provided by the well-known superconcentrator technique (for $d = 2, 3$ and for even $d \geq 4$). Cherukhin's method was formalized by Jukna as a general lower-bound criterion for Boolean operators, the "Strong Multiscale Entropy" (SME) property. It seemed plausible that this property could imply significantly better lower bounds by an improved analysis. However, we show that this is not the case, by exhibiting an explicit operator with the SME property that is computable in depth $d$ with $O(n \cdot \lambda_{d - 1}(n))$ wires, for $d = 2, 3$ and for even $d \geq 6$.
Next, we show limitations of two simpler lower-bound criteria given by Jukna: the "entropy method" for general operators, and the "pairwise-distance method" for linear operators. We show that neither method gives super-linear lower bounds for depth 3. In the process, we obtain the first known polynomial separation between the depth-2 and depth-3 wire complexities for an explicit operator. We also continue the study (initiated by Jukna) of the complexity of "representing" a linear operator by bounded-depth circuits, a weaker notion than computing the operator.Fri, 18 May 2012 07:49:29 +0300https://eccc.weizmann.ac.il/report/2011/125#revision1
Comment 1
| (fixable) bug in version 1, Lemma 13 |
Andrew Drucker
https://eccc.weizmann.ac.il/report/2011/125#comment1While preparing the camera-ready version, I found a bug in the proof of the result on limitations of the SME lower-bound criterion. Fortunately, it is fixable by a small modification of the original approach, recovering the theorem as stated.
I will put a revision up ASAP (in ~1 week), along with an explanation of the issue.Thu, 12 Apr 2012 07:10:19 +0300https://eccc.weizmann.ac.il/report/2011/125#comment1
Paper TR11-125
| Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators |
Andrew Drucker
https://eccc.weizmann.ac.il/report/2011/125We study the circuit complexity of Boolean operators, i.e., collections of Boolean functions defined over a common input. Our focus is the well-studied model in which arbitrary Boolean functions are allowed as gates, and in which a circuit's complexity is measured by its depth and number of wires. We show sharp limitations of several existing lower-bound methods for this model.
First, we study an information-theoretic lower-bound method due to Cherukhin, that yields bounds of form $\Omega_d(n \cdot \lambda_{d - 1}(n))$ on the number of wires needed to compute cyclic convolutions in depth $d \geq 2$. This was the first improvement over the lower bounds provided by the well-known superconcentrator technique (for $d = 2, 3$ and for even $d \geq 4$). Cherukhin's method was formalized by Jukna as a general lower-bound criterion for Boolean operators, the "Strong Multiscale Entropy" (SME) property. It seemed plausible that this property could imply significantly better lower bounds by an improved analysis. However, we show that this is not the case, by exhibiting an explicit operator with the SME property that is computable in depth $d$ with $O(n \cdot \lambda_{d - 1}(n))$ wires, for $d = 2, 3$ and for even $d \geq 6$.
Next, we show limitations of two simpler lower-bound criteria given by Jukna: the "entropy method" for general operators, and the "pairwise-distance method" for linear operators. We show that neither method gives super-linear lower bounds for depth 3. In the process, we obtain the first known polynomial separation between the depth-2 and depth-3 wire complexities for an explicit operator. We also continue the study (initiated by Jukna) of the complexity of "representing" a linear operator by bounded-depth circuits, a weaker notion than computing the operator.Fri, 16 Sep 2011 17:28:39 +0300https://eccc.weizmann.ac.il/report/2011/125