On the Relationship between Energy Complexity and Other Boolean Function Measures
share
In this work we investigate into energy complexity, a Boolean function measure related to circuit complexity. Given a circuit C over the standard basis {∨_2,∧_2,}, the energy complexity of C, denoted by EC(C), is the maximum number of its activated inner gates over all inputs. The energy complexity of a Boolean function f, denoted by EC(f), is the minimum of EC(C) over all circuits C computing f. This concept has attracted lots of attention in literature. Recently, Denish, Otiv, and Sarma [COCOON'18] gave EC(f) an upper bound in terms of the decision tree complexity, EC(f)=O(D(f)^3). They also showed that EC(f)≤ 3n-1, where n is the input size. Recall that the minimum size of circuit to compute f could be as large as 2^n/n. We improve their upper bounds by showing that EC(f)≤{1/2D(f)^2+O(D(f)),n+2D(f)-2}. For the lower bound, Denish, Otiv, and Sarma defined positive sensitivity, a complexity measure denoted by psens(f), and showed that EC(f)>1/3psens(f). They asked whether EC(f) can also be lower bounded by a polynomial of D(f). In this paper we affirm it by proving EC(f)=Ω(√(D(f))). For non-degenerated functions with input size n, we give another lower bound EC(f)=Ω(n). All these three lower bounds are incomparable to each other. Besides, we also examine the energy complexity of OR functions and ADDRESS functions, which implies the tightness of our two lower bounds respectively. In addition, the former one answers another open question asking for a non-trivial lower bounds for the energy complexity of OR functions.
READ FULL TEXT