Entropy of contact circuits and lower bounds on their complexity (Q1109754)

A new concept of entropy H(A) of a discrete object A (circuit, Boolean function, etc.) is used to obtain lower bounds on contact circuit complexity of Boolean functions. Intuitively, an entropy must ensure two constraints: (i) \(size(S)\geq \delta^{-1}H(S)\) for any circuit S and some small \(\delta >0\) (independent of S), i.e. no step of computation makes more than \(\delta\) information; and (ii) if S computes f then H(S)\(\geq H(f)\), i.e. any circuit contains not less information than its function. Then \(\delta^{-1}H(f)\) is the lower bound for L(f), the circuit size complexity of f. In well-known Andreev-Razborov's approach the entropy H(A) is defined as the distance \(\rho\) (A,\({\mathfrak A})\) of A from a special class of objects \({\mathfrak A}\). Then (ii) is trivial, and (i) is the main step of this approach. In the paper under review the entropy \(H^{\phi}(A)\) is defined to be the maximum number of ``unsimilar'' subobjects of A with respect to an appropriate relation of ``similarity'' \(\phi\). Then, for some \(\phi\), (i) becomes trivial with \(H(S)=H^{\phi}(S)\). To prove (ii), special relations \(\psi\) are found such that \(H^{\phi}(S)\geq H^{\psi}(f)\). (This is done via an entropy- preserving embedding of circuits into the more restricted ones). Hence, \(L(f)\geq \delta^{-1}H(f)\). In particular, this new argument allows to prove in a uniform and easy way that contact circuits (as well as branching programs) with bounded number of null-chains require \(\exp_ 2(\Omega (\sqrt{n}))\) size to compute some explicitly defined n-argument Boolean functions.