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

摘要

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.