On the relationship between energy complexity and other boolean function measures

Xiaoming Sun (), Yuan Sun (), Kewen Wu () and Zhiyu Xia ()
Additional contact information
Xiaoming Sun: Chinese Academy of Sciences
Yuan Sun: Chinese Academy of Sciences
Kewen Wu: Peking University
Zhiyu Xia: Chinese Academy of Sciences

Journal of Combinatorial Optimization, 2022, vol. 43, issue 5, No 25, 1470-1492

Abstract: Abstract We focus on energy complexity, a Boolean function measure related closely to Boolean circuit design. Given a circuit $$\mathcal {C}$$ C over the standard basis $$\{\vee _2,\wedge _2,\lnot \}$$ { ∨ 2 , ∧ 2 , ¬ } , the energy complexity of $$\mathcal {C}$$ C , denoted by $${{\,\mathrm{EC}\,}}(\mathcal {C})$$ EC ( C ) , is the maximum number of its activated inner gates over all inputs. The energy complexity of a Boolean function f, denoted by $${{\,\mathrm{EC}\,}}(f)$$ EC ( f ) , is the minimum of $${{\,\mathrm{EC}\,}}(\mathcal {C})$$ EC ( C ) over all circuits $$\mathcal {C}$$ C computing f. Recently, K. Dinesh et al. (International computing and combinatorics conference, Springer, Berlin, 738–750, 2018) gave $${{\,\mathrm{EC}\,}}(f)$$ EC ( f ) an upper bound by the decision tree complexity, $${{\,\mathrm{EC}\,}}(f)=O({{\,\mathrm{D}\,}}(f)^3)$$ EC ( f ) = O ( D ( f ) 3 ) . On the input size n, They also showed that $${{\,\mathrm{EC}\,}}(f)$$ EC ( f ) is at most $$3n-1$$ 3 n - 1 . For the lower bound side, they showed that $${{\,\mathrm{EC}\,}}(f)\ge \frac{1}{3}{{\,\mathrm{psens}\,}}(f)$$ EC ( f ) ≥ 1 3 psens ( f ) , where $${{\,\mathrm{psens}\,}}(f)$$ 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 $${{\,\mathrm{EC}\,}}(f)=\varOmega (\sqrt{{{\,\mathrm{D}\,}}(f)})$$ EC ( f ) = Ω ( D ( f ) ) , which answers the above open problem. For upper bounds, $${{\,\mathrm{EC}\,}}(f)\le \min \{\frac{1}{2}{{\,\mathrm{D}\,}}(f)^2+O({{\,\mathrm{D}\,}}(f)),n+2{{\,\mathrm{D}\,}}(f)-2\}$$ EC ( f ) ≤ min { 1 2 D ( f ) 2 + O ( D ( f ) ) , n + 2 D ( f ) - 2 } holds. For non-degenerated functions, we also provide another lower bound $${{\,\mathrm{EC}\,}}(f)=\varOmega (\log {n})$$ EC ( f ) = Ω ( log n ) where n is the input size. We also discuss the energy complexity of two specific function classes, $$\mathtt {OR}$$ OR functions and $$\mathtt {ADDRESS}$$ 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 $$\mathtt {OR}$$ OR functions.

Keywords: Energy complexity; Decision tree; Boolean function; Circuit complexity. (search for similar items in EconPapers)
Date: 2022
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-020-00689-8 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:43:y:2022:i:5:d:10.1007_s10878-020-00689-8

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-020-00689-8

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().