A tighter relation between sensitivity complexity and certificate complexity

doi:10.1016/j.tcs.2018.08.025

	A tighter relation between sensitivity complexity and certificate complexity
	He, Kun 1,2; Li, Qian 3; Sun, Xiaoming 1,2
	2019-03-01
发表期刊	THEORETICAL COMPUTER SCIENCE
ISSN	0304-3975
卷号	762 页码:1-12
摘要	The sensitivity conjecture proposed by Nisan and Szegedy in 1994, which asserts that for any Boolean function, its sensitivity complexity is polynomially related to the block sensitivity complexity, is one of the most important and challenging problems in the study of decision tree complexity, Despite a lot of efforts, the best known upper bound of block sensitivity, as well as the certificate complexity, is still exponential in terms of sensitivity. In this paper, we give a better upper bound for certificate complexity and block sensitivity, bs(f) <= C(f) <= (8/9 +0(1))s(f)2(s(f)-1)where bs(f), C(f) and s(f) are the block sensitivity, certificate complexity and sensitivity, respectively. The proof is based on a deep investigation on the structure of the sensitivity graph. We also provide a tighter relationship between the 0-certificate complexity C-0(f) and 0-sensitivity s(0)(f) for functions with small 1-sensitivity s(1)(f). (C) 2018 Elsevier B.V. All rights reserved.
关键词	Sensitivity conjecture Sensitivity Block sensitivity Certificate complexity Boolean functions
DOI	10.1016/j.tcs.2018.08.025
收录类别	SCI
语种	英语
资助项目	National Natural Science Foundation of China[61433014] ; National Natural Science Foundation of China[61502449] ; National Natural Science Foundation of China[61602440] ; 973 Program of China[2016YFB1000201] ; China National Program for support of Top-notch Young Professionals
WOS研究方向	Computer Science
WOS类目	Computer Science, Theory & Methods
WOS记录号	WOS:000459528200001
出版者	ELSEVIER SCIENCE BV
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/3419
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	He, Kun
作者单位	1.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing 100190, Peoples R China 2.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 3.Alibaba Grp, Hangzhou 310052, Zhejiang, Peoples R China
推荐引用方式 GB/T 7714	He, Kun,Li, Qian,Sun, Xiaoming. A tighter relation between sensitivity complexity and certificate complexity[J]. THEORETICAL COMPUTER SCIENCE,2019,762:1-12.
APA	He, Kun,Li, Qian,&Sun, Xiaoming.(2019).A tighter relation between sensitivity complexity and certificate complexity.THEORETICAL COMPUTER SCIENCE,762,1-12.
MLA	He, Kun,et al."A tighter relation between sensitivity complexity and certificate complexity".THEORETICAL COMPUTER SCIENCE 762(2019):1-12.