On the Sensitivity Conjecture

Author Avishay Tal



PDF
Thumbnail PDF

File

LIPIcs.ICALP.2016.38.pdf
  • Filesize: 0.49 MB
  • 13 pages

Document Identifiers

Author Details

Avishay Tal

Cite AsGet BibTex

Avishay Tal. On the Sensitivity Conjecture. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 55, pp. 38:1-38:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.ICALP.2016.38

Abstract

The sensitivity of a Boolean function f:{0,1}^n -> {0,1} is the maximal number of neighbors a point in the Boolean hypercube has with different f-value. Roughly speaking, the block sensitivity allows to flip a set of bits (called a block) rather than just one bit, in order to change the value of f. The sensitivity conjecture, posed by Nisan and Szegedy (CC, 1994), states that the block sensitivity, bs(f), is at most polynomial in the sensitivity, s(f), for any Boolean function f. A positive answer to the conjecture will have many consequences, as the block sensitivity is polynomially related to many other complexity measures such as the certificate complexity, the decision tree complexity and the degree. The conjecture is far from being understood, as there is an exponential gap between the known upper and lower bounds relating bs(f) and s(f). We continue a line of work started by Kenyon and Kutin (Inf. Comput., 2004), studying the l-block sensitivity, bs_l(f), where l bounds the size of sensitive blocks. While for bs_2(f) the picture is well understood with almost matching upper and lower bounds, for bs_3(f) it is not. We show that any development in understanding bs_3(f) in terms of s(f) will have great implications on the original question. Namely, we show that either bs(f) is at most sub-exponential in s(f) (which improves the state of the art upper bounds) or that bs_3(f) >= s(f){3-epsilon} for some Boolean functions (which improves the state of the art separations). We generalize the question of bs(f) versus s(f) to bounded functions f:{0,1}^n -> [0,1] and show an analog result to that of Kenyon and Kutin: bs_l(f) = O(s(f))^l. Surprisingly, in this case, the bounds are close to being tight. In particular, we construct a bounded function f:{0,1}^n -> [0, 1] with bs(f) n/log(n) and s(f) = O(log(n)), a clear counterexample to the sensitivity conjecture for bounded functions. Finally, we give a new super-quadratic separation between sensitivity and decision tree complexity by constructing Boolean functions with DT(f) >= s(f)^{2.115}. Prior to this work, only quadratic separations, DT(f) = s(f)^2, were known.
Keywords
  • sensitivity conjecture
  • decision tree
  • block sensitivity

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads

References

  1. A. Ambainis, M. Bavarian, Y. Gao, J. Mao, X. Sun, and S. Zuo. Tighter relations between sensitivity and other complexity measures. In ICALP (1), pages 101-113, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_9.
  2. A. Ambainis and K. Prusis. A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity. In MFCS, pages 33-44, 2014. Google Scholar
  3. A. Ambainis, K. Prusis, and J. Vihrovs. Sensitivity versus certificate complexity of boolean functions. CoRR, abs/1503.07691, 2015. Google Scholar
  4. A. Ambainis and X. Sun. New separation between s(f) and bs(f). Electronic Colloquium on Computational Complexity (ECCC), 18:116, 2011. Google Scholar
  5. A. Ambainis and J. Vihrovs. Size of sets with small sensitivity: A generalization of simon’s lemma. In Theory and Applications of Models of Computation - 12th Annual Conference, TAMC 2015, Singapore, May 18-20, 2015, Proceedings, pages 122-133, 2015. Google Scholar
  6. M. Boppana. Lattice variant of the sensitivity conjecture. Electronic Colloquium on Computational Complexity (ECCC), 19:89, 2012. Google Scholar
  7. H. Buhrman and R. de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21-43, 2002. Google Scholar
  8. S. Chakraborty. On the sensitivity of cyclically-invariant boolean functions. Discrete Mathematics & Theoretical Computer Science, 13(4):51-60, 2011. Google Scholar
  9. J. Gilmer, M. Koucký, and M. E. Saks. A new approach to the sensitivity conjecture. In Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science, ITCS 2015, Rehovot, Israel, January 11-13, 2015, pages 247-254, 2015. Google Scholar
  10. P. Gopalan, N. Nisan, R. A. Servedio, K. Talwar, and A. Wigderson. Smooth boolean functions are easy: Efficient algorithms for low-sensitivity functions. In ITCS, pages 59-70, 2016. Google Scholar
  11. P. Hatami, R. Kulkarni, and D. Pankratov. Variations on the sensitivity conjecture. Theory of Computing, Graduate Surveys, 2:1-27, 2011. Google Scholar
  12. C. Kenyon and S. Kutin. Sensitivity, block sensitivity, and l-block sensitivity of boolean functions. Inf. Comput., 189(1):43-53, 2004. URL: http://dx.doi.org/10.1016/j.ic.2002.12.001.
  13. N. Nisan. Crew prams and decision trees. In STOC, pages 327-335, 1989. URL: http://dx.doi.org/10.1145/73007.73038.
  14. N. Nisan and M. Szegedy. On the degree of Boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. Google Scholar
  15. D. Rubinstein. Sensitivity vs. block sensitivity of boolean functions. Combinatorica, 15(2):297-299, 1995. URL: http://dx.doi.org/10.1007/BF01200762.
  16. H. U. Simon. A tight Ω(log log n)-bound on the time for parallel ram’s to compute nondegenerated boolean functions. In Foundations of computation theory, pages 439-444. Springer, 1983. Google Scholar
  17. M. Szegedy. An O(n^0.4732) upper bound on the complexity of the GKS communication game. Electronic Colloquium on Computational Complexity (ECCC), 22:102, 2015. Google Scholar
  18. A. Tal. Properties and applications of boolean function composition. In ITCS, pages 441-454, 2013. Google Scholar
  19. A. Tal. On the sensitivity conjecture. Electronic Colloquium on Computational Complexity (ECCC), 23:62, 2016. Google Scholar
  20. M. Virza. Sensitivity versus block sensitivity of boolean functions. Inf. Process. Lett., 111(9):433-435, 2011. URL: http://dx.doi.org/10.1016/j.ipl.2011.02.001.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail