Header menu link for other important links
X
New bounds for energy complexity of boolean functions
, S. Otiv, J. Sarma
Published in Springer Verlag
2018
Volume: 10976 LNCS
   
Pages: 738 - 750
Abstract
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). © 2018, Springer International Publishing AG, part of Springer Nature.