A tighter relation between sensitivity complexity and certificate complexity

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, b s ( f ) ≤ C ( f ) ≤ ( 8 9 + o ( 1 ) ) s ( f ) 2 s ( f ) − 1, where b s ( 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 ).

Authors

• Kun He
• Qian Li Beijing Advanced Innovation Center for Big Data and Brain Computing, Beihang University, China School of Computer Science and Engineering, Beihang University, China
• Xiaoming Sun

Keywords

• Sensitivity conjecture
• Sensitivity
• Block sensitivity
• Certificate complexity
• Boolean functions