Document Open Access Logo

On the Sensitivity Conjecture for Disjunctive Normal Forms

Authors Karthik C. S., Sébastien Tavenas

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2016.15.pdf
  • Filesize: 0.53 MB
  • 15 pages

Document Identifiers

Author Details

Karthik C. S.
Sébastien Tavenas

Cite As Get BibTex

Karthik C. S. and Sébastien Tavenas. On the Sensitivity Conjecture for Disjunctive Normal Forms. In 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 65, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.FSTTCS.2016.15

Abstract

The sensitivity conjecture of Nisan and Szegedy [CC'94] asks whether for any Boolean function f, the maximum sensitivity s(f), is polynomially related to its block sensitivity bs(f), and hence to other major complexity measures. Despite major advances in the analysis of Boolean functions over the last decade, the problem remains widely open. 

In this paper, we consider a restriction on the class of Boolean functions through a model of computation (DNF), and refer to the functions adhering to this restriction as admitting the Normalized Block property. We prove that for any function f admitting the Normalized Block property, bs(f) <= 4 * s(f)^2. We note that (almost) all the functions mentioned in literature that achieve a quadratic separation between sensitivity and block sensitivity admit the Normalized Block property.  
 
Recently, Gopalan et al. [ITCS'16] showed that every Boolean function f is uniquely specified by its values on a Hamming ball of radius at most 2 * s(f). We extend this result and also construct examples of Boolean functions which provide the matching lower bounds.

Subject Classification

Keywords
  • Boolean function
  • Sensitivity
  • Block sensitivity
  • DNF

Metrics

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

References

  1. Andris Ambainis, Mohammad Bavarian, Yihan Gao, Jieming Mao, Xiaoming Sun, and Song Zuo. Tighter relations between sensitivity and other complexity measures. In Automata, Languages, and Programming - 41st International Colloquium, ICALP 2014, Copenhagen, Denmark, July 8-11, 2014, Proceedings, Part I, pages 101-113, 2014. URL: http://dx.doi.org/10.1007/978-3-662-43948-7_9.
  2. 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.
  3. Andris Ambainis and Xiaoming Sun. New separation between s(f) and bs(f). Electronic Colloquium on Computational Complexity (ECCC), 18:116, 2011. URL: http://eccc.hpi-web.de/report/2011/116.
  4. 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, August 22-26, 2016 - Kraków, Poland, pages 16:1-16:14, 2016. URL: http://dx.doi.org/10.4230/LIPIcs.MFCS.2016.16.
  5. 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.
  6. Sourav Chakraborty. On the sensitivity of cyclically-invariant boolean functions. Discrete Mathematics &Theoretical Computer Science, 13(4):51-60, 2011. Google Scholar
  7. Stephen A. Cook and Cynthia Dwork. Bounds on the time for parallel ram’s to compute simple functions. In Proceedings of the 14th Annual ACM Symposium on Theory of Computing, May 5-7, 1982, San Francisco, California, USA, pages 231-233, 1982. URL: http://dx.doi.org/10.1145/800070.802196.
  8. Stephen A. 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. URL: http://dx.doi.org/10.1137/0215006.
  9. Andrew Drucker. Block sensitivity of minterm-transitive functions. Theor. Comput. Sci., 412(41):5796-5801, 2011. URL: http://dx.doi.org/10.1016/j.tcs.2011.06.025.
  10. Justin Gilmer, Michael Saks, and Srikanth Srinivasan. Composition limits and separating examples for some boolean function complexity measures. In 2013 IEEE Conference on Computational Complexity, pages 185-196. IEEE, 2013. Google Scholar
  11. Parikshit Gopalan, Noam Nisan, Rocco A. Servedio, Kunal Talwar, and Avi Wigderson. Smooth boolean functions are easy: Efficient algorithms for low-sensitivity functions. In Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, Cambridge, MA, USA, January 14-16, 2016, pages 59-70, 2016. URL: http://dx.doi.org/10.1145/2840728.2840738.
  12. Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. Variations on the sensitivity conjecture. Theory of Computing, Graduate Surveys, 4:1-27, 2011. URL: http://dx.doi.org/10.4086/toc.gs.2011.004.
  13. Claire Kenyon and Samuel 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.
  14. Chengyu Lin and Shengyu Zhang. Sensitivity conjecture and log-rank conjecture for functions with small alternating numbers. CoRR, abs/1602.06627, 2016. URL: http://arxiv.org/abs/1602.06627.
  15. Noam Nisan. CREW prams and decision trees. SIAM J. Comput., 20(6):999-1007, 1991. URL: http://dx.doi.org/10.1137/0220062.
  16. Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4:301-313, 1994. URL: http://dx.doi.org/10.1007/BF01263419.
  17. David Rubinstein. Sensitivity vs. block sensitivity of boolean functions. Combinatorica, 15(2):297-299, 1995. URL: http://dx.doi.org/10.1007/BF01200762.
  18. Xiaoming Sun. Block sensitivity of weakly symmetric functions. Theor. Comput. Sci., 384(1):87-91, 2007. URL: http://dx.doi.org/10.1016/j.tcs.2007.05.020.
  19. Madars 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.
  20. Ingo Wegener. The critical complexity of all (monotone) boolean functions and monotone graph properties. Information and Control, 67(1-3):212-222, 1985. URL: http://dx.doi.org/10.1016/S0019-9958(85)80036-X.
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