Header menu link for other important links
X
New bounds for energy complexity of Boolean functions
, S. Otiv, J. Sarma
Published in Elsevier B.V.
2020
Volume: 845
   
Pages: 59 - 75
Abstract
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)=defminC⁡ECB(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.
About the journal
JournalData powered by TypesetTheoretical Computer Science
PublisherData powered by TypesetElsevier B.V.
ISSN03043975