Header menu link for other important links
New Bounds for Energy Complexity of Boolean Functions
, Otiv Samir, Krishnamoorthy Dinesh
Published in Springer International Publishing
Pages: 738 - 750

For a Boolean function f:{0,1}n→{0,1}f:{0,1}n{0,1} computed by a circuit C over a finite basis BB, the energy complexity of C (denoted by ECB(C)ECB(C)) is the maximum over all inputs {0,1}n{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 BB denoted by Open image in new window

where C is a circuit over BB computing f.

We study the case when B={∧2,∨2,¬}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))3n(1+ϵ(n)) for a small ϵ(n)ϵ(n)(which we observe is improvable to 3n−13n1). 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)EC(f)O(DT(f)3) where DT(f)DT(f) is the optimal decision tree depth of f.

We define a parameter positive sensitivity (denoted by psenspsens), 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)/3EC(C)psens(f)/3.

Restricting the above notion of energy complexity to Boolean formulas, denoted ECF(f)ECF(f), we show that ECF(f)=Θ(L(f))ECF(f)=Θ(L(f)) 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 Ω(n−−√)Ω(n). We show that any unbounded fan-in circuit of depth 3 computing the parity on n variables must have energy is Ω(n)Ω(n).

About the journal
JournalData powered by TypesetInternational Computing and Combinatorics Conference
PublisherData powered by TypesetSpringer International Publishing
Open AccessNo