Limitations of Lower-Bound Methods for the Wire Complexity of Boolean Operators

Andrew Drucker

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We 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 super concentrator 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 $\cO(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 pair wise-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.
Original language English Proceedings of the 27th Conference on Computational Complexity, CCC 2012, Porto, Portugal, June 26-29, 2012 Institute of Electrical and Electronics Engineers (IEEE) 170-180 11 978-0-7695-4708-4 https://doi.org/10.1109/CCC.2012.39 Published - Jun 2012