Document Open Access Logo

On the Sensitivity Conjecture for Read-k Formulas

Authors Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, Ameya Velingker

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2016.16.pdf
  • Filesize: 467 kB
  • 14 pages

Document Identifiers

Author Details

Mitali Bafna
Satyanarayana V. Lokam
Sébastien Tavenas
Ameya Velingker

Cite As Get BibTex

Mitali Bafna, Satyanarayana V. Lokam, Sébastien Tavenas, and Ameya Velingker. On the Sensitivity Conjecture for Read-k Formulas. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 16:1-16:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.MFCS.2016.16

Abstract

Various combinatorial/algebraic parameters are used to quantify the complexity of a Boolean function. Among them, sensitivity is one of the simplest and  block sensitivity is one of the most useful. Nisan (1989) and Nisan and Szegedy (1991) showed that block sensitivity and several other parameters, such as certificate complexity, decision tree depth, and degree over R, are all polynomially related to one another. The sensitivity conjecture states that there is also a polynomial relationship between sensitivity and block sensitivity, thus supplying the "missing link".

Since its introduction in 1991, the sensitivity conjecture has remained a challenging open question in the study of Boolean functions. One natural approach is to prove it for special classes of functions. For instance, the conjecture is known to be true for monotone functions, symmetric functions, and
functions describing graph properties.

In this paper, we consider the conjecture for Boolean functions computable by read-k formulas. A read-k formula is a tree in which each variable appears at most k times among the leaves and has Boolean gates at its internal nodes. We show that the sensitivity conjecture holds for read-once formulas with gates computing symmetric functions. We next consider regular formulas with OR and AND gates. A formula is regular if it is a leveled tree with all gates at a given level having the same fan-in and computing the same function. We prove the sensitivity conjecture for constant depth regular read-k formulas for constant k.

Subject Classification

Keywords
  • sensitivity conjecture
  • read-k formulas
  • analysis of Boolean functions

Metrics

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

References

  1. Scott Aaronson. The "sensitivity" of 2-colorings of the d-dimensional integer lattice. blogpost, July 2010. URL: http://mathoverflow.net/questions/31482/.
  2. Noga Alon and Joel H Spencer. The Probabilistic Method. John Wiley and Sons, 1994. Google Scholar
  3. Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo. Tighter relations between sensitivity and other complexity measures. In International Colloquium on Automata, Languages and Programming (ICALP) 2014, Part I, pages 101-113, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_9.
  4. Andris Ambainis and Krisjanis Prusis. A tight lower bound on certificate complexity in terms of block sensitivity and sensitivity. In Mathematical Foundations of Computer Science 2014 - 39th International Symposium, MFCS 2014, Budapest, Hungary, August 25-29, 2014. Proceedings, Part II, pages 33-44, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_4.
  5. Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca, and Ronald de Wolf. Quantum lower bounds by polynomials. In 39th Annual Symposium on Foundations of Computer Science, FOCS '98, November 8-11, 1998, Palo Alto, California, USA, pages 352-361, 1998. URL: http://dx.doi.org/10.1109/SFCS.1998.743485.
  6. Meena Boppana. Lattice variant of the sensitivity conjecture. Electronic Colloquium on Computational Complexity (ECCC), 19:89, 2012. Google Scholar
  7. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: a survey. Theor. Comput. Sci., 288(1):21-43, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00144-X.
  8. Sourav Chakraborty. On the sensitivity of cyclically-invariant boolean functions. In Conference on Computational Complexity (CCC), pages 163-167, 2005. Google Scholar
  9. Stephen Cook, Cynthia Dwork, and Rüdiger Reischuk. Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput., 15(1):87-97, 1986. Google Scholar
  10. Justin Gilmer, Michal Koucký, and Michael E. Saks. A new approach to the sensitivity conjecture. In Innovations in Theoretical Computer Science, ITCS, pages 247-254, 2015. Google Scholar
  11. Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, and Avi Wigderson. Degree and sensitivity: tails of two distributions. to appear CCC 2016, 2016. Google Scholar
  12. Craig Gotsman and Nathan Linial. The equivalence of two problems on the cube. Journal of Combinatorial Theory, Series A, 61(1):142-146, 1992. Google Scholar
  13. Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. Variations on the sensitivity conjecture. Theory of Computing, Graduate Surveys, 4:1-27, 2011. Google Scholar
  14. Claire Kenyon and Samuel Kutin. Sensitivity, block sensitivity, and l-block sensitivity of Boolean functions. Information and Computation, 189(1):43-53, 2004. Google Scholar
  15. Hiroki Morizumi. Sensitivity, block sensitivity, and certificate complexity of unate functions and read-once functions. IFIP TCS, 2014. Google Scholar
  16. Noam Nisan. CREW PRAMs and decision trees. In Symposium on Theory of Computing, pages 327-335, 1989. Google Scholar
  17. Noam Nisan and Mario Szegedy. On the degree of Boolean functions as real polynomial. In Symposium on Theory of Computing, pages 462-467, 1992. Google Scholar
  18. David Rubinstein. Sensitivity vs. block sensitivity of boolean functions. Combinatorica, 15(2):297-299, 1995. Google Scholar
  19. Hans-Ulrich Simon. A tight Ω(log log n)-bound on the time for parallel RAM’s to compute nondegenerated Boolean functions. Foundations of Computation Theory, Lecture Notes in Computer Science, 158(1):439-444, 1983. Google Scholar
  20. Xiaoming Sun. Block sensitivity of weakly symmetric functions. Theor. Comput. Sci., 384(1):87-91, 2007. Google Scholar
  21. Avishay Tal. On the sensitivity conjecture. In International Colloquium on Automata, Languages and Programming (ICALP), 2016. Google Scholar
  22. György Turán. The critical complexity of graph properties. Inf. Process. Lett., 18(3):151-153, 1984. Google Scholar
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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact