New bounds for energy complexity of Boolean functions

For a Boolean function f:{0, 1}(n) ->{0, 1} computed by a Boolean circuit Cover a finite basis B, the energy complexityof C(denoted by ECB(C)) is the maximum over all inputs {0, 1}(n) of the number gates of the circuit C(excluding the inputs) that output a one. Energy Complexity of a Boolean function over a finite basis Bdenoted by ECB(f) (def)= min(C) ECB(C) where Cis a Boolean circuit over Bcomputing f. We study the case when B={boolean AND(2), boolean OR(2), (sic)}, the standard Boolean basis. It is known that any Boolean function can be computed by a circuit (with potentially large size) with an energy of at most 3n(1 + is an element of(n)) for a small is an element of(n)(which we observe is improvable to 3n - 1). We show several new results and connections between energy complexity and other wellstudied parameters of Boolean functions. For all Boolean functions f, EC(f) <= O(DT(f)(3)) where DT(f) is the optimal decision tree depth of f. We define a parameter positive sensitivity(denoted by psens), a quantity that is smaller than sensitivity (Cook et al. 1986, [3]) and defined in a similar way, and show that for any Boolean circuit Ccomputing a Boolean function f, EC(C) >= psens(f)/3. For a monotone function f, we show that EC(f) = Omega(KW+ (f)) where KW+ (f) is the cost of monotone Karchmer-Wigderson game of f. Restricting the above notion of energy complexity to Boolean formulas, we show EC(F) = Omega(root L(F)-Depth(F)) where L(F) is the size and Depth(F) is the depth of a formula F. (C) 2020 Elsevier B.V. All rights reserved.