Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR18-153 | 22nd August 2018 06:31

New Bounds for Energy Complexity of Boolean Functions


Authors: Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma
Publication: 2nd September 2018 07:38
Downloads: 109


For a Boolean function $f:\{0,1\}^n \to \{0,1\}$ computed by a circuit $C$ over a finite basis $\cal{B}$, the energy complexity of $C$ (denoted by $\mathbf{EC}_{{\cal B}}(C)$) is the maximum over all inputs $\{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 ${\cal B}$ denoted by $\mathbf{EC}_{\cal B}(f):= \min_C \mathbf{EC}_{{\cal B}}(C)$ where $C$ is a circuit over ${\cal B}$ computing $f$.

We study the case when ${\cal B} = \{\land_2, \lor_2, \lnot\}$, 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+\epsilon(n))$ for a small $ \epsilon(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.

1. For all Boolean functions $f$, $\mathbf{EC}(f) \le O({DT}(f)^3)$ where ${DT}(f)$ is the optimal decision tree depth of $f$.

2. We define a parameter {positive sensitivity} (denoted by $\mathbf{psens}$), 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$, $ \mathbf{EC}(C) \ge \mathbf{psens}(f)/3$.

3. For a monotone function $f$, we show that $\mathbf{EC}(f) = \Omega(\mathbf{KW}^+(f))$ where $\mathbf{KW}^+(f)$ is the cost of monotone Karchmer-Wigderson game of $f$.

4. Restricting the above notion of energy complexity to Boolean formulas, we show $\mathbf{EC}(F) = \Omega\left (\sqrt{L(F)}-depth(F)\right )$ where $L(F)$ is the size and $depth(F)$ is the depth of a formula $F$.

ISSN 1433-8092 | Imprint