Jayalal Sarma

For a Boolean function f:{0,1}n→{0,1} computed by a Boolean circuit C over a finite basis B, the energy complexity of 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 B denoted by ECB(f)=defminC⁡ECB(C) where C is a Boolean circuit over B computing f. We study the case when B={∧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 3n(1+ϵ(n)) for a small ϵ(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, 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 C computing a Boolean function f, EC(C)≥psens(f)/3. • For a monotone function f, we show that EC(f)=Ω(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)=Ω(L(F)−Depth(F)) where L(F) is the size and Depth(F) is the depth of a formula F.

For a Boolean function (Formula Presented) computed by a circuit C over a finite basis (Formula Presented), the energy complexity of C (denoted by (Formula Presented)) is the maximum over all inputs (Formula Presented) 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 (Formula Presented) denoted by where C is a circuit over (Formula Presented) computing f. We study the case when (Formula Presented), 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 (Formula Presented) for a small (Formula Presented) (which we observe is improvable to (Formula Presented)). We show several new results and connections between energy complexity and other well-studied parameters of Boolean functions. For all Boolean functions f, (Formula Presented) where (Formula Presented) is the optimal decision tree depth of f.We define a parameter positive sensitivity (denoted by (Formula Presented)), 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, (Formula Presented).Restricting the above notion of energy complexity to Boolean formulas, denoted (Formula Presented), we show that (Formula Presented) where L(f) is the minimum size of a formula computing f. We next prove lower bounds on energy for explicit functions. In this direction, we show that for the perfect matching function on an input graph of n edges, any Boolean circuit with bounded fan-in must have energy (Formula Presented). We show that any unbounded fan-in circuit of depth 3 computing the parity on n variables must have energy is (Formula Presented).