Get all the updates for this publication

Other

New Bounds for Energy Complexity of Boolean FunctionsPublished in Springer International Publishing

2018

Pages: 738 - 750

For a Boolean function f:{0,1}n→{0,1}$f:\{0,1{\}}^{n}\to \{0,1\}$ 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}}(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 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}=\{{\wedge}_{2},{\vee}_{2},\mathrm{\neg}\}$, 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+\u03f5(n))$ for a small ϵ(n)$\u03f5(n)$(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}(f)\le O(\mathsf{D}\mathsf{T}(f{)}^{3})$ where DT(f)$\mathsf{D}\mathsf{T}(f)$ 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}(C)\ge \mathsf{p}\mathsf{s}\mathsf{e}\mathsf{n}\mathsf{s}(f)/3$.

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

Topics: Image (category theory) (60)%60% related to the paper, Energy (signal processing) (53)%53% related to the paper and Boolean function (52)%52% related to the paper

View more info for "New Bounds for Energy Complexity of Boolean Functions"

Content may be subject to copyright.

About the journal

Journal | Data powered by TypesetInternational Computing and Combinatorics Conference |
---|---|

Publisher | Data powered by TypesetSpringer International Publishing |

Open Access | No |