On the relationship between energy complexity and other boolean function measures

doi:10.1007/s10878-020-00689-8

	On the relationship between energy complexity and other boolean function measures
	Sun, Xiaoming 1,2; Sun, Yuan 1,2; Wu, Kewen 3; Xia, Zhiyu 1,2
	2021-01-07
发表期刊	JOURNAL OF COMBINATORIAL OPTIMIZATION
ISSN	1382-6905
页码	23
摘要	We focus on energy complexity, a Boolean function measure related closely to Boolean circuit design. Given a circuit C over the standard basis {boolean OR(2), Lambda(2), (sic)}, 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 3n - 1. For the lower bound side, they showed that EC(f) >= 1/3 psens(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) = Omega(root D(f)), which answers the above open problem. - For upper bounds, EC(f) <= min{1/2 D(f)(2) + O(D(f)), n + 2D(f) - 2} holds. - For non-degenerated functions, we also provide another lower bound EC(f) = Omega(log n) 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.
关键词	Energy complexity Decision tree Boolean function Circuit complexity
DOI	10.1007/s10878-020-00689-8
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61433014] ; National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61761136014] ; National Natural Science Foundation of China[61872334] ; National Natural Science Foundation of China[61502449] ; National Natural Science Foundation of China[61602440] ; National Natural Science Foundation of China[61801459] ; 973 Program of China[2016YFB1000201] ; K. C. Wong Education Foundation
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Interdisciplinary Applications ; Mathematics, Applied
WOS记录号	WOS:000605896800003
出版者	SPRINGER
引用统计	被引频次：7[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/16372
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Sun, Yuan
作者单位	1.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing, Peoples R China 2.Univ Chinese Acad Sci, Beijing, Peoples R China 3.Peking Univ, Sch Elect Engn & Comp Sci, Beijing, Peoples R China
推荐引用方式 GB/T 7714	Sun, Xiaoming,Sun, Yuan,Wu, Kewen,et al. On the relationship between energy complexity and other boolean function measures[J]. JOURNAL OF COMBINATORIAL OPTIMIZATION,2021:23.
APA	Sun, Xiaoming,Sun, Yuan,Wu, Kewen,&Xia, Zhiyu.(2021).On the relationship between energy complexity and other boolean function measures.JOURNAL OF COMBINATORIAL OPTIMIZATION,23.
MLA	Sun, Xiaoming,et al."On the relationship between energy complexity and other boolean function measures".JOURNAL OF COMBINATORIAL OPTIMIZATION (2021):23.