Tighter Relations Between Sensitivity and Other Complexity Measures
作者： Andris Ambainis , Song Zuo , Jieming Mao , Yihan Gao , Xiaoming Sun
DOI:
关键词:
摘要: The sensitivity conjecture of Nisan and Szegedy [12] asks whether the maximum sensitivity of a Boolean function is polynomially related to the other major complexity measures of …
arxiv.org
springer.com参考文章(10)
L.H. Harper, Optimal numberings and isoperimetric problems on graphs Journal of Combinatorial Theory, Series A. ,vol. 1, pp. 385- 393 ,(1966) , 10.1016/S0021-9800(66)80059-5
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
F.R.K Chung, Zoltán Füredi, R.L Graham, P Seymour, On induced subgraphs of the cube Journal of Combinatorial Theory, Series A. ,vol. 49, pp. 180- 187 ,(1988) , 10.1016/0097-3165(88)90034-9
Andris Ambainis, Kaspars Balodis, Scott Aaronson, Mohammad Bavarian, Weak Parity arXiv: Computational Complexity. ,(2013)
Béla Bollobás, Combinatorics: Set Systems, Hypergraphs, Families of Vectors and Combinatorial Probability ,(1986)
Hans-Ulrich Simon, A Tight Omega(loglog n)-Bound on the Time for Parallel Ram's to Compute Nondegenerated Boolean Functions fundamentals of computation theory. pp. 439- 444 ,(1983) , 10.1007/3-540-12689-9_124
Noam Nisan, Mario Szegedy, On the degree of Boolean functions as real polynomials Computational Complexity. ,vol. 4, pp. 301- 313 ,(1994) , 10.1007/BF01263419
C Gotsman, N Linial, The equivalence of two problems on the cube Journal of Combinatorial Theory, Series A. ,vol. 61, pp. 142- 146 ,(1992) , 10.1016/0097-3165(92)90060-8
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
David Rubinstein, SENSITIVITY VS. BLOCK SENSITIVITY OF BOOLEAN FUNCTIONS Combinatorica. ,vol. 15, pp. 297- 299 ,(1995) , 10.1007/BF01200762