6533b7d5fe1ef96bd1263c21
RESEARCH PRODUCT
Sensitivity Versus Certificate Complexity of Boolean Functions
Andris AmbainisJevgăźnijs VihrovsKrišjăźnis Prźsissubject
Discrete mathematicsConjectureStructure (category theory)Block (permutation group theory)0102 computer and information sciences02 engineering and technologyFunction (mathematics)01 natural sciencesUpper and lower boundsExponential functionCombinatorics010201 computation theory & mathematics0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingSensitivity (control systems)Boolean functionMathematicsdescription
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 the certificate complexity is polynomially related to sensitivity. Previously, it has been shown that $$bsf \le Cf \le 2^{sf-1} sf - sf-1$$. In this work, we give a better upper bound of $$bsf \le Cf \le \max \left 2^{sf-1}\left sf-\frac{1}{3}\right , sf\right $$ using a recent theorem limiting the structure of function graphs. We also examine relations between these measures for functions with 1-sensitivity $$s_1f=2$$ and arbitrary 0-sensitivity $$s_0f$$.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2016-01-01 |