A Tighter Relation between Sensitivity and Certificate Complexity

2016/09/14 by Kun He, Qian Li, He, Kun +3
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences

paper · pdf · doi:10.48550/arxiv.1609.04342

openalex publication_date 2016/09/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The sensitivity conjecture which claims that the sensitivity complexity is polynomially related to block sensitivity complexity, is one of the most important and challenging problem in decision tree complexity theory. Despite of a lot of efforts, the best known upper bound of block sensitivity, as well as the certificate complexity, are still exponential in terms of sensitivity: bs(f)≤ C(f)≤max\2^s(f)-1(s(f)-(1)/(3)),s(f)\. In this paper, we give a better upper bound of bs(f)≤ C(f)≤((8)/(9) + o(1))s(f)2^{s(f) - 1}. The proof is based on a deep investigation on the structure of the sensitivity graph. We also provide a tighter relationship between C₀(f) and s₀(f) for functions with s₁(f)=2.

Related

• Sensitivity versus Certificate Complexity of Boolean Functions
• New upper bound on block sensitivity and certificate complexity in terms of sensitivity
• Tighter Relations Between Sensitivity and Other Complexity Measures
• Relations between monotone complexity measures based on decision tree complexity
• Low-Sensitivity Functions from Unambiguous Certificates