X
New Bounds for Energy Complexity of Boolean Functions
Otiv Samir, Krishnamoorthy Dinesh
Published in Springer International Publishing
2018
Pages: 738 - 750
Abstract

For a Boolean function f:{0,1}n→{0,1}$f:\left\{0,1{\right\}}^{n}\to \left\{0,1\right\}$ computed by a circuit C over a finite basis B$\mathcal{B}$, the energy complexity of C (denoted by ECB(C)${\mathsf{E}\mathsf{C}}_{\mathcal{B}}\left(C\right)$) is the maximum over all inputs {0,1}n$\left\{0,1{\right\}}^{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 B$\mathcal{B}$ denoted by Open image in new window

where C is a circuit over B$\mathcal{B}$ computing f.

We study the case when B={∧2,∨2,¬}$\mathcal{B}=\left\{{\wedge }_{2},{\vee }_{2},\mathrm{¬}\right\}$, 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\left(1+ϵ\left(n\right)\right)$ for a small ϵ(n)$ϵ\left(n\right)$(which we observe is improvable to 3n−1$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)$\mathsf{E}\mathsf{C}\left(f\right)\le O\left(\mathsf{D}\mathsf{T}\left(f{\right)}^{3}\right)$ where DT(f)$\mathsf{D}\mathsf{T}\left(f\right)$ is the optimal decision tree depth of f.

We define a parameter positive sensitivity (denoted by psens$\mathsf{p}\mathsf{s}\mathsf{e}\mathsf{n}\mathsf{s}$), 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$\mathsf{E}\mathsf{C}\left(C\right)\ge \mathsf{p}\mathsf{s}\mathsf{e}\mathsf{n}\mathsf{s}\left(f\right)/3$.

Restricting the above notion of energy complexity to Boolean formulas, denoted ECF(f)$\mathsf{E}{\mathsf{C}}^{\mathsf{F}}\left(f\right)$, we show that ECF(f)=Θ(L(f))$\mathsf{E}{\mathsf{C}}^{\mathsf{F}}\left(f\right)=\Theta \left(L\left(f\right)\right)$ 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−−√)$\Omega \left(\sqrt{n}\right)$. We show that any unbounded fan-in circuit of depth 3 computing the parity on n variables must have energy is Ω(n)$\Omega \left(n\right)$.