Get all the updates for this publication

Articles

New bounds for energy complexity of Boolean functionsPublished in Elsevier B.V.

2020

Volume: 845

Pages: 59 - 75

For a Boolean function f:{0,1}n→{0,1} computed by a Boolean circuit C over a finite basis B, the energy complexity of C (denoted by ECB(C)) is the maximum over all inputs {0,1}n of the number gates of the circuit C (excluding the inputs) that output a one. Energy Complexity of a Boolean function over a finite basis B denoted by ECB(f)=defminCECB(C) where C is a Boolean circuit over B computing f. We study the case when B={∧2,∨2,¬}, 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)) for a small ϵ(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. • For all Boolean functions f, EC(f)≤O(DT(f)3) where DT(f) is the optimal decision tree depth of f. • We define a parameter positive sensitivity (denoted by psens), a quantity that is smaller than sensitivity (Cook et al. 1986, [3]) and defined in a similar way, and show that for any Boolean circuit C computing a Boolean function f, EC(C)≥psens(f)/3. • For a monotone function f, we show that EC(f)=Ω(KW+(f)) where KW+(f) is the cost of monotone Karchmer-Wigderson game of f. • Restricting the above notion of energy complexity to Boolean formulas, we show EC(F)=Ω(L(F)−Depth(F)) where L(F) is the size and Depth(F) is the depth of a formula F. © 2020 Elsevier B.V.

Postprint Version

Content may be subject to copyright,Check License© This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc... ...© This manuscript version is made available under the CC-BY-NC-ND 4.0 license https://creativecommons.org/licenses/by-nc-nd/4.0/

About the journal

Journal | Data powered by TypesetTheoretical Computer Science |
---|---|

Publisher | Data powered by TypesetElsevier B.V. |

ISSN | 03043975 |