Document Open Access Logo

New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity

Authors Siddhesh Chaubal, Anna Gál

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2018.13.pdf
  • Filesize: 439 kB
  • 16 pages

Document Identifiers

Author Details

Siddhesh Chaubal
  • University of Texas at Austin, USA
Anna Gál
  • University of Texas at Austin, USA

Cite As Get BibTex

Siddhesh Chaubal and Anna Gál. New Constructions with Quadratic Separation between Sensitivity and Block Sensitivity. In 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 122, pp. 13:1-13:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018) https://doi.org/10.4230/LIPIcs.FSTTCS.2018.13

Abstract

Nisan and Szegedy [Nisan and Szegedy, 1994] conjectured that block sensitivity is at most polynomial in sensitivity for any Boolean function. There is a huge gap between the best known upper bound on block sensitivity in terms of sensitivity - which is exponential, and the best known separating examples - which give only a quadratic separation between block sensitivity and sensitivity.
In this paper we give various new constructions of families of Boolean functions that exhibit quadratic separation between sensitivity and block sensitivity. Our constructions have several novel aspects. For example, we give the first direct constructions of families of Boolean functions that have both 0-block sensitivity and 1-block sensitivity quadratically larger than sensitivity.

Subject Classification

ACM Subject Classification
  • Theory of computation → Complexity classes
Keywords
  • Sensitivity Conjecture
  • Boolean Functions
  • Complexity Measures

Metrics

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

References

  1. Andris Ambainis. Polynomial degree vs. quantum query complexity. J. Comput. Syst. Sci., 72(2):220-238, 2006. URL: http://dx.doi.org/10.1016/j.jcss.2005.06.006.
  2. 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.
  3. 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.
  4. Andris Ambainis, Krišjānis Prūsis, and Jevgēnijs Vihrovs. Sensitivity Versus Certificate Complexity of Boolean Functions. In Computer Science - Theory and Applications, pages 16-28, Cham, 2016. URL: http://dx.doi.org/10.1007/978-3-319-34171-2_2.
  5. 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.
  6. Harry Buhrman and Ronald De Wolf. Complexity measures and decision tree complexity: a survey. Theoretical Computer Science, 288(1):21-43, 2002. URL: http://dx.doi.org/10.1016/S0304-3975(01)00144-X.
  7. Sourav Chakraborty. On the Sensitivity of Cyclically-Invariant Boolean Functions. CoRR, abs/cs/0501026, 2005. URL: http://arxiv.org/abs/cs/0501026,
  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. Justin Gilmer, Michael Saks, and Srikanth Srinivasan. Composition limits and separating examples for some boolean function complexity measures. Combinatorica, 36(3):265-311, June 2016. URL: http://dx.doi.org/10.1007/s00493-014-3189-x.
  10. Parikshit Gopalan, Rocco A. Servedio, Avishay Tal, and Avi Wigderson. Degree and Sensitivity: tails of two distributions. CoRR, abs/1604.07432, 2016. URL: http://arxiv.org/abs/1604.07432.
  11. 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.
  12. Claire Kenyon and Samuel Kutin. Sensitivity, Block Sensitivity, and L-block Sensitivity of Boolean Functions. Inf. Comput., 189(1):43-53, February 2004. URL: http://dx.doi.org/10.1016/j.ic.2002.12.001.
  13. Noam Nisan. CREW PRAMs and decision trees. SIAM J. Comput., 20(6):999-1007, 1991. URL: http://dx.doi.org/10.1137/0220062.
  14. Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. Computational Complexity, 4(4):301-313, December 1994. URL: http://dx.doi.org/10.1007/BF01263419.
  15. David Rubinstein. Sensitivity vs. block sensitivity of Boolean functions. Combinatorica, 15(2):297-299, June 1995. URL: http://dx.doi.org/10.1007/BF01200762.
  16. Hans-Ulrich Simon. A tight ω(loglog n)-bound on the time for parallel RAM’s to compute nondegenerated boolean functions. Information and Control, 55(1):102-107, 1982. URL: http://dx.doi.org/10.1016/S0019-9958(82)90477-6.
  17. Avishay Tal. Properties and applications of boolean function composition. In Innovations in Theoretical Computer Science, ITCS '13, Berkeley, CA, USA, January 9-12, 2013, pages 441-454, 2013. URL: http://dx.doi.org/10.1145/2422436.2422485.
  18. Avishay Tal. Personal communication, 2018. Google Scholar
  19. Madars Virza. Sensitivity versus block sensitivity of Boolean functions. Information Processing Letters, 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
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact