Skip to main content
eScholarship
Open Access Publications from the University of California

UC Berkeley

UC Berkeley Previously Published Works bannerUC Berkeley

On the relationship between energy complexity and other boolean function measures

Published Web Location

https://arxiv.org/abs/1810.03811
No data is associated with this publication.
Abstract

We focus on energy complexity, a Boolean function measure related closely to Boolean circuit design. Given a circuit C over the standard basis { ∨ 2, ∧ 2, ¬ } , the energy complexity of C, denoted by EC(C), is the maximum number of its activated inner gates over all inputs. The energy complexity of a Boolean function f, denoted by EC(f), is the minimum of EC(C) over all circuits C computing f. Recently, K. Dinesh et al. (International computing and combinatorics conference, Springer, Berlin, 738–750, 2018) gave EC(f) an upper bound by the decision tree complexity, EC(f)=O(D(f)3). On the input size n, They also showed that EC(f) is at most 3 n- 1. For the lower bound side, they showed that EC(f)≥13psens(f), where psens(f) is called positive sensitivity. A remained open problem is whether the energy complexity of a Boolean function has a polynomial relationship with its decision tree complexity. Our results for energy complexity can be listed below.For the lower bound, we prove the equation that EC(f)=Ω(D(f)), which answers the above open problem.For upper bounds, EC(f)≤min{12D(f)2+O(D(f)),n+2D(f)-2} holds.For non-degenerated functions, we also provide another lower bound EC(f)=Ω(logn) where n is the input size.We also discuss the energy complexity of two specific function classes, OR functions and ADDRESS functions, which implies the tightness of our two lower bounds respectively. In addition, the former one answers another open question in Dinesh et al. (International computing and combinatorics conference, Springer, Berlin, 738–750, 2018) asking for non-trivial lower bound for energy complexity of OR functions.

Many UC-authored scholarly publications are freely available on this site because of the UC's open access policies. Let us know how this access is important for you.

Item not freely available? Link broken?
Report a problem accessing this item