New Bounds for Energy Complexity of Boolean Functions

摘要

For a Boolean function f : 0 1 n 0 1 computed by a circuit C over a finite basis , the energy complexity of C (denoted by EC ( C ) ) is the maximum over all inputs 0 1 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 denoted by EC ( f ) : = min C EC ( C ) where C is a circuit over computing f .We study the case when = 2 2 , 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 3 n (1 + ( n )) for a small ( n ) (which we observe is improvable to 3 n ? 1 ). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions.1. For all Boolean functions f , EC ( f ) O ( D T ( f ) 3 ) where D T ( f ) is the optimal decision tree depth of f . 2. We define a parameter {positive sensitivity} (denoted by 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 , EC ( C ) psens ( f ) 3 .3. For a monotone function f , we show that EC ( f ) = ( K W + ( f )) where K W + ( f ) is the cost of monotone Karchmer-Wigderson game of f .4. Restricting the above notion of energy complexity to Boolean formulas, we show EC ( F ) = L ( F ) ? d epth ( F ) where L ( F ) is the size and depth ( F ) is the depth of a formula F .