2015/03/26 by Andris Ambainis, Ambainis, Andris, Krišjānis Prūsis +3
Computer Science · #Coding theory and cryptography #Complexity and Algorithms in Graphs #Quantum Computing Algorithms and Architecture #cs.CC
paper · pdf · doi:10.48550/arxiv.1503.07691
arxiv created 2015/06/08 · arxiv updated 2015/06/09
Sensitivity, block sensitivity and certificate complexity are basic complexity measures of Boolean functions. The famous sensitivity conjecture claims that sensitivity is polynomially related to block sensitivity. However, it has been notoriously hard to obtain even exponential bounds. Since block sensitivity is known to be polynomially related to certificate complexity, an equivalent of proving this conjecture would be showing that certificate complexity is polynomially related to sensitivity. Previously, it has been shown that bs(f) ≤ C(f) ≤ 2s(f)-1 s(f) - (s(f)-1). In this work, we give a better upper bound of bs(f) ≤ C(f) ≤ max(2s(f)-1(s(f)-\frac 1 3), s(f)) using a recent theorem limiting the structure of function graphs. We also examine relations between these measures for functions with small 1-sensitivity s1(f) and arbitrary 0-sensitivity s0(f).