ECCC-Report TR18-153https://eccc.weizmann.ac.il/report/2018/153Comments and Revisions published for TR18-153en-usSun, 13 Sep 2020 12:35:09 +0300
Revision 1
| New Bounds for Energy Complexity of Boolean Functions |
Krishnamoorthy Dinesh,
Samir Otiv,
Jayalal Sarma
https://eccc.weizmann.ac.il/report/2018/153#revision1For 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$.
Sun, 13 Sep 2020 12:35:09 +0300https://eccc.weizmann.ac.il/report/2018/153#revision1
Paper TR18-153
| New Bounds for Energy Complexity of Boolean Functions |
Krishnamoorthy Dinesh,
Jayalal Sarma,
Samir Otiv
https://eccc.weizmann.ac.il/report/2018/153For 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$.
Sun, 02 Sep 2018 07:38:07 +0300https://eccc.weizmann.ac.il/report/2018/153