Abstract

\textbackslash newcommand\textbackslash EC\textbackslash mathsfEC\textbackslash newcommand\textbackslash KW\textbackslash mathsfKW\textbackslash newcommand\textbackslash DT\textbackslash mathsfDT\textbackslash newcommand\textbackslash psens\textbackslash mathsfpsens \textbackslash newcommand\textbackslash calB\textbackslash cal B For a Boolean function f:\textbackslash0,1\textbackslash\^n \textbackslash to \textbackslash0,1\textbackslash computed by a circuit C over a finite basis \textbackslash mathcalB, the energy complexity of C (denoted by \textbackslash EC\textbackslash calB(C)) is the maximum over all inputs \textbackslash0,1\textbackslash\^n the numbers of gates of the circuit C (excluding the inputs) that output a one. Energy Complexity of a Boolean function over a finite basis \textbackslash calB denoted by \textbackslash EC\textbackslash calB(f):= \textbackslash minC \textbackslash EC\textbackslash calB(C) where C is a circuit over \textbackslash calB computing f. We study the case when \textbackslash calB = \textbackslash\textbackslash land2, \textbackslash lor2, \textbackslash lnot\textbackslash, 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+\textbackslash epsilon(n)) for a small \textbackslash epsilon(n)(which we observe is improvable to 3n-1). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions. * For all Boolean functions f, \textbackslash EC(f) \textbackslash le O(\textbackslash DT(f)\^3) where \textbackslash DT(f) is the optimal decision tree depth of f. * We define a parameter \textbackslash textitpositive sensitivity (denoted by \textbackslash psens), a quantity that is smaller than sensitivity and defined in a similar way, and show that for any Boolean circuit C computing a Boolean function f, \textbackslash EC(C) \textbackslash ge \textbackslash psens(f)/3. * For a monotone function f, we show that \textbackslash EC(f) = \textbackslash Omega(\textbackslash KW\^+(f)) where \textbackslash KW\^+(f) is the cost of monotone Karchmer-Wigderson game of f. * Restricting the above notion of energy complexity to Boolean formulas, we show \textbackslash EC(F) = \textbackslash Omega\textbackslash left (\textbackslash sqrtL(F)-depth(F)\textbackslash right ) where L(F) is the size and depth(F) is the depth of a formula F.