Revision #1 Authors: Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

Accepted on: 13th September 2020 12:35

Downloads: 340

Keywords:

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$.

Improved presentation of Theorem 1.5. Added an improvement due to Sun et.al. and a comparison to their result (in Section 6)

TR18-153 Authors: Krishnamoorthy Dinesh, Samir Otiv, Jayalal Sarma

Publication: 2nd September 2018 07:38

Downloads: 779

Keywords:

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$.