Tighter Relations Between Sensitivity and Other Complexity Measures

Part of book or chapter of book, Preprint English OPEN
Ambainis, Andris; Bavarian, Mohammad; Gao, Yihan; Mao, Jieming; Sun, Xiaoming; Zuo, Song;
  • Journal: International Colloqium on Automata, Languages and Programming (ICALP'2014) (issn: 0302-9743)
  • Related identifiers: doi: 10.1007/978-3-662-43948-7_9
  • Subject: Computer Science - Computational Complexity

Sensitivity conjecture is a longstanding and fundamental open problem in the area of complexity measures of Boolean functions and decision tree complexity. The conjecture postulates that the maximum sensitivity of a Boolean function is polynomially related to other majo... View more
  • References (13)
    13 references, page 1 of 2

    [2] S. Aaronson, A. Ambainis, K. Balodis and M. Bavarian. Weak Parity. ICALP (1) 2014: 26-38.

    [3] A. Ambainis and X. Sun. New separation between spf q and bspf q. Electronic Colloquium on Computational Complexity (ECCC) 18: 116 (2011).

    [4] B. Bollob´as. Combinatorics: set systems, hypergraphs, families of vectors and combinatorial probability. Cambridge University Press, Cambridge, 1986.

    [5] H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey, Theoretical Computer Science 288(1): 21-43, 2002.

    [6] F. R. K. Chung, Z. Fu¨redi, R.L. Graham and P. Seymour. On induced subgraphs of the cube, J. Comb. Theory Ser. A, 49 (1988).

    [7] D. Falik and A. Samorodnitsky. Edge-isoperimetric inequalities and influences. Combinatorics, Probability & Computing, 16.5 (2007): 693-712.

    [8] C. Gotsman and N. Linial. The equivalence of two problems on the cube. Journal of Combinatorial Theory, Series A, 61(1), 142-146 (1992).

    [9] L. Harper, Optimal numberings and isoperimetric problems on graphs, Journal of Combinatorial Theory, 1 (1966).

    [10] P. Hatami, R. Kulkarni, D. Pankratov. Variations on the Sensitivity Conjecture, Theory of Computing Library, Graduate Surveys No. 4 (2011) pp. 1-27.

    [11] C. Kenyon, S. Kutin. Sensitivity, block sensitivity, and l-block sensitivity of Boolean functions. Information and Computation, 189(1): 43-53, 2004.

  • Metrics
    No metrics available
Share - Bookmark