A Tighter Relation between Sensitivity and Certificate Complexity
作者： Xiaoming Sun , Kun He , Qian Li
DOI:
关键词: Graph 、 Upper and lower bounds 、 Discrete mathematics 、 Exponential function 、 Conjecture 、 Mathematics 、 Combinatorics
摘要: 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 …
harvard.edu
arxiv.org参考文章(13)
Meena Boppana, Lattice Variant of the Sensitivity Conjecture arXiv: Combinatorics. ,(2012)
Noam Nisan, CREW PRAMs and decision trees SIAM Journal on Computing. ,vol. 20, pp. 999- 1007 ,(1991) , 10.1137/0220062
Noam Nisan, Mario Szegedy, On the degree of Boolean functions as real polynomials Computational Complexity. ,vol. 4, pp. 301- 313 ,(1994) , 10.1007/BF01263419
Stephen Cook, Cynthia Dwork, Bounds on the time for parallel RAM's to compute simple functions Proceedings of the fourteenth annual ACM symposium on Theory of computing - STOC '82. pp. 231- 233 ,(1982) , 10.1145/800070.802196
Justin Gilmer, Michal Koucký, Michael E. Saks, A New Approach to the Sensitivity Conjecture conference on innovations in theoretical computer science. pp. 247- 254 ,(2015) , 10.1145/2688073.2688096
Harry Buhrman, Ronald de Wolf, Complexity measures and decision tree complexity: a survey Theoretical Computer Science. ,vol. 288, pp. 21- 43 ,(2002) , 10.1016/S0304-3975(01)00144-X
Stephen Cook, Cynthia Dwork, Rüdiger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes SIAM Journal on Computing. ,vol. 15, pp. 87- 97 ,(1986) , 10.1137/0215006
György Turán, The critical complexity of graph properties Information Processing Letters. ,vol. 18, pp. 151- 153 ,(1984) , 10.1016/0020-0190(84)90019-X
Claire Kenyon, Samuel Kutin, Sensitivity, block sensitivity, and l-block sensitivity of boolean functions Information & Computation. ,vol. 189, pp. 43- 53 ,(2004) , 10.1016/J.IC.2002.12.001
S. Chakraborty, On the Sensitivity of Cyclically-Invariant Boolean Functions 20th Annual IEEE Conference on Computational Complexity (CCC'05). pp. 163- 167 ,(2005) , 10.1109/CCC.2005.38