Document Open Access Logo

Sensitivity Lower Bounds from Linear Dependencies

Authors Sophie Laplante, Reza Naserasr, Anupa Sunny

PDF
Thumbnail PDF

File

LIPIcs.MFCS.2020.62.pdf
  • Filesize: 462 kB
  • 14 pages

Document Identifiers

Author Details

Sophie Laplante
  • Université de Paris, IRIF, France
Reza Naserasr
  • Université de Paris, CNRS, IRIF, France
Anupa Sunny
  • Université de Paris, IRIF, France

Funding

This work is supported by the ANR-France project HOSIGRA (ANR-17-CE40-0022). This project has received funding from the European Union’s Horizon 2020 research and innovation program under the Marie Sklodowska-Curie grant agreement No 754362.

Cite AsGet BibTex

Sophie Laplante, Reza Naserasr, and Anupa Sunny. Sensitivity Lower Bounds from Linear Dependencies. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.MFCS.2020.62

Abstract

Recently, using spectral techniques, H. Huang proved that every subgraph of the hypercube of dimension n induced on more than half the vertices has maximum degree at least √n. Combined with some earlier work, this completed a proof of the sensitivity conjecture. In this work we show how to derive a proof of Huang’s result using only linear dependency and independence of vectors associated with the vertices of the hypercube. Our approach leads to several improvements of the result. In particular we prove that in any induced subgraph of H_n with more than half the number of vertices, there are two vertices, one of odd parity and the other of even parity, each with at least n vertices at distance at most 2. As an application we show that for any Boolean function f, the polynomial degree of f is bounded above by s₀(f) s₁(f), a strictly stronger statement which implies the sensitivity conjecture.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational complexity and cryptography
Keywords
  • Boolean Functions
  • Polynomial Degree
  • Sensitivity

Metrics

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

Related Versions

References

  1. Scott Aaronson, Shalev Ben-David, Robin Kothari, and Avishay Tal. Quantum implications of huang’s sensitivity theorem. CoRR, abs/2004.13231, 2020. URL: http://arxiv.org/abs/2004.13231.
  2. Bahman Ahmadi, Fatemeh Alinaghipour, Shaun Cavers, Michael S.and Fallat, Karen Meagher, and Shahla Nasserasr. Minimum number of distinct eigenvalues of graphs. Electronic Journal of Linear Algebra, 26(45):673-691, 2013. URL: https://doi.org/10.13001/1081-3810.1679.
  3. Harry Buhrman and Ronald de Wolf. Complexity measures and decision tree complexity: A survey. Theor. Comput. Sci., 288(1):21-43, October 2002. URL: https://doi.org/10.1016/S0304-3975(01)00144-X.
  4. Sourav Chakraborty. Sensitivity, block sensitivity and certificate complexity of boolean functions. Master’s thesis, The University of Chicago, 2010. Google Scholar
  5. Sourav Chakraborty. On the sensitivity of cyclically-invariant Boolean functions. Discrete Mathematics & Theoretical Computer Science, Vol. 13 no. 4, 2011. URL: https://dmtcs.episciences.org/552.
  6. F. R. K. Chung, Zoltán Füredi, R.L Graham, and P. Seymour. On induced subgraphs of the cube. Journal of Combinatorial Theory, Series A, 49(1):180-187, 1988. URL: https://doi.org/10.1016/0097-3165(88)90034-9.
  7. C Gotsman and N Linial. The equivalence of two problems on the cube. Journal of Combinatorial Theory, Series A, 61(1):142-146, 1992. URL: https://doi.org/10.1016/0097-3165(92)90060-8.
  8. Yingfei Gu and Xiao-Liang Qi. Majorana fermions and the sensitivity conjecture. arXiv 1908.06322, 2019. URL: http://arxiv.org/abs/1908.06322.
  9. Pooya Hatami, Raghav Kulkarni, and Denis Pankratov. Variations on the Sensitivity Conjecture. Number 4 in Graduate Surveys. Theory of Computing Library, 2011. URL: https://doi.org/10.4086/toc.gs.2011.004.
  10. Hao Huang. Induced subgraphs of hypercubes and a proof of the sensitivity conjecture. Annals of Mathematics, 190(3):949-955, 2019. URL: https://www.jstor.org/stable/10.4007/annals.2019.190.3.6.
  11. Roman Karasev. Huang’s theorem and the exterior algebra. Technical Report 1907.11175, arXiv, 2019. URL: http://arxiv.org/abs/1907.11175.
  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: https://doi.org/10.1016/j.ic.2002.12.001.
  13. Donald E. Knuth. A computational proof of Huang’s degree theorem, 2019. Manuscript, 28 July, revised 3 August, https://www.cs.stanford.edu/ knuth/papers/huang.pdf. URL: https://www.cs.stanford.edu/~knuth/papers/huang.pdf.
  14. Daniel V. Mathews. The sensitivity conjecture, induced subgraphs of cubes, and clifford algebras. arXiv 1907.12357, 2019. URL: http://arxiv.org/abs/1907.12357.
  15. Noam Nisan and Mario Szegedy. On the degree of boolean functions as real polynomials. In Proceedings of the Twenty-fourth Annual ACM Symposium on Theory of Computing, STOC '92, pages 462-467, New York, NY, USA, 1992. ACM. URL: https://doi.org/10.1145/129712.129757.
  16. Avishay Tal. Properties and applications of boolean function composition. In Proceedings of the 4th Conference on Innovations in Theoretical Computer Science, ITCS '13, pages 441-454, New York, NY, USA, 2013. ACM. URL: https://doi.org/10.1145/2422436.2422485.
  17. Terence Tao. Twisted convolution and the sensitivity conjecture. What’s New? (26 July, 2019), 2019. Google Scholar
  18. Thomas Zaslavsky. Signed graphs. Discrete Applied Mathematics, 4(1):47-74, 1982. URL: https://doi.org/10.1016/0166-218X(82)90033-6.
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 Imprint Privacy Contact