Energy and Output Patterns in Boolean Circuits

Consider a Boolean circuit over a basis \(\{ \wedge , \vee , \lnot \}\) , where \(\wedge \) and \(\vee \) are the conjunction of unbounded fan-in and disjunction of unbounded fan-in, respectively, and \(\lnot \) is the negation. The energy complexity of a circuit is defined as the number of gates outputting ones in the circuit, where the maximum is taken over all the input assignments. We prove that the number of output patterns (the set of possible outputs of all the internal gates in the circuit) in a circuit of energy e is at most \(2^{e \log e + 4e}\) vastly improving the trivial bound of \({s \atopwithdelims ()e}\) where s is the size of the circuit. Building on this tool, we prove the following: