Energy and fan-in of logic circuits computing symmetric Boolean functions

In this paper, we consider a logic circuit (i.e., a combinatorial circuit consisting of gates, each of which computes a Boolean function) C computing a symmetric Boolean function f, and investigate a relationship between two complexity measures, energy e and fan-in l of C, where the energy e is the maximum number of gates outputting “1” over all inputs to C, and the fan-in l is the maximum number of inputs of every gate in C. We first prove that any symmetric Boolean function f of n variables can be computed by a logic circuit of energy e=O(n/l) and fan-in l, and then provide an almost tight lower bound e≥⌈(n−mf)/l⌉ where mf is the maximum numbers of consecutive “0”s or “1”s in the value vector of f. Our results imply that there exists a tradeoff between the energy and fan-in of logic circuits computing a symmetric Boolean function.