Back to Search
Start Over
A tighter relation between sensitivity complexity and certificate complexity.
- Source :
-
Theoretical Computer Science . Mar2019, Vol. 762, p1-12. 12p. - Publication Year :
- 2019
-
Abstract
- Abstract 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). [ABSTRACT FROM AUTHOR]
- Subjects :
- *SENSITIVITY analysis
*ALGORITHMS
*POLYNOMIALS
*BOOLEAN algebra
*MATHEMATICS
Subjects
Details
- Language :
- English
- ISSN :
- 03043975
- Volume :
- 762
- Database :
- Academic Search Index
- Journal :
- Theoretical Computer Science
- Publication Type :
- Academic Journal
- Accession number :
- 134531333
- Full Text :
- https://doi.org/10.1016/j.tcs.2018.08.025