Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

Abstract

In this paper, we show that every $(2^{n-1}+1)$-vertex induced subgraph of the $n$-dimensional cube graph has maximum degree at least $\sqrt {n}$. This is the best possible result, and it improves a logarithmic lower bound shown by Chung, Füredi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.

  • [ambainis-sun] Go to document A. Ambainis and X. Sun, "New separation between $s(f)$ and $bs(f)$," Electronic Colloquium on Computational Complexity (ECCC), vol. 18, p. 116, 2011.
    @ARTICLE{ambainis-sun,
      author = {Ambainis, A. and Sun, X.},
      title = {New separation between $s(f)$ and $bs(f)$},
      journal = {Electronic Colloquium on Computational Complexity (ECCC)},
      volume = {18},
      pages = {116},
      year = {2011},
      url = {https://eccc.weizmann.ac.il/report/2011/116/},
      zblnumber = {},
      }
  • [survey_bw] Go to document H. Buhrman and R. de Wolf, "Complexity measures and decision tree complexity: a survey," in Complexity and Logic, , 2002, vol. 288, pp. 21-43.
    @INCOLLECTION{survey_bw,
      author = {Buhrman, Harry and de Wolf, Ronald},
      title = {Complexity measures and decision tree complexity: a survey},
      booktitle = {Complexity and Logic },
      venue = {Vienna, 1998},
      journal = {Theoret. Comput. Sci.},
      fjournal = {Theoretical Computer Science},
      volume = {288},
      year = {2002},
      pages = {21--43},
      issn = {0304-3975},
      mrclass = {68Q15 (81P68)},
      mrnumber = {1934888},
      mrreviewer = {Anna Bernasconi},
      doi = {10.1016/S0304-3975(01)00144-X},
      url = {https://doi.org/10.1016/S0304-3975(01)00144-X},
      zblnumber = {1061.68058},
      }
  • [cfgs_cube] Go to document F. R. K. Chung, Z. Füredi, R. L. Graham, and P. Seymour, "On induced subgraphs of the cube," J. Combin. Theory Ser. A, vol. 49, iss. 1, pp. 180-187, 1988.
    @ARTICLE{cfgs_cube,
      author = {Chung, F. R. K. and Füredi, Zolt\'{a}n and Graham, R. L. and Seymour, P.},
      title = {On induced subgraphs of the cube},
      journal = {J. Combin. Theory Ser. A},
      fjournal = {Journal of Combinatorial Theory. Series A},
      volume = {49},
      year = {1988},
      number = {1},
      pages = {180--187},
      issn = {0097-3165},
      mrclass = {05C10 (03G05 05C35 06E30 68Q25)},
      mrnumber = {0957216},
      mrreviewer = {O. D'Antona},
      doi = {10.1016/0097-3165(88)90034-9},
      url = {https://doi.org/10.1016/0097-3165(88)90034-9},
      zblnumber = {0653.05037},
      }
  • [drucker] A. Drucker, A note on a communication game, 2017.
    @MISC{drucker,
      author = {Drucker, A.},
      title = {A note on a communication game},
      arxiv = {1706.07890},
      year = {2017},
      zblnumber = {},
      }
  • [fisk] Go to document S. Fisk, "A very short proof of Cauchy’s interlace theorem for eigenvalues of Hermitian matrices," Amer. Math. Monthly, vol. 112, iss. 2, p. 118, 2005.
    @ARTICLE{fisk,
      author = {Fisk, S.},
      title = {A very short proof of {C}auchy's interlace theorem for eigenvalues of {H}ermitian matrices},
      journal = {Amer. Math. Monthly},
      volume = { 112},
      year = {2005},
      number = {2},
      pages = {118},
      zblnumber = {},
      url = {https://doi.org/10.2307/30037409},
      doi = {10.2307/30037409},
     }
  • [GKS] Go to document J. Gilmer, M. Koucký, and M. Saks, "A new approach to the sensitivity conjecture," in ITCS’15—Proceedings of the 6th Innovations in Theoretical Computer Science, 2015, pp. 247-254.
    @INPROCEEDINGS{GKS,
      author = {Gilmer, Justin and Kouck\'{y},
      Michal and Saks, Michael},
      title = {A new approach to the sensitivity conjecture},
      booktitle = {I{TCS}'15---{P}roceedings of the 6th {I}nnovations in {T}heoretical {C}omputer {S}cience},
      pages = {247--254},
      publisher = {ACM, New York},
      year = {2015},
      mrclass = {94D05},
      mrnumber = {3419015},
      mrreviewer = {Anant P. Godbole},
      zblnumber = {1364.68197},
      url = {https://doi.org/10.1145/2688073.2688096},
      doi = {10.1145/2688073.2688096},
      }
  • [GNSTW] Go to document 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’16—Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science, 2016, pp. 59-70.
    @INPROCEEDINGS{GNSTW,
      author = {Gopalan, Parikshit and Nisan, Noam and Servedio, Rocco A. and Talwar, Kunal and Wigderson, Avi},
      title = {Smooth {B}oolean functions are easy: efficient algorithms for low-sensitivity functions},
      booktitle = {I{TCS}'16---{P}roceedings of the 2016 {ACM} {C}onference on {I}nnovations in {T}heoretical {C}omputer {S}cience},
      pages = {59--70},
      publisher = {ACM, New York},
      year = {2016},
      mrclass = {94D05 (68Q15)},
      mrnumber = {3629811},
      zblnumber = {1334.68068},
      url = {https://doi.org/10.1145/2840728.2840738},
      doi = {10.1145/2840728.2840738},
      }
  • [GSW] Go to document P. Gopalan, R. A. Servedio, and A. Wigderson, "Degree and sensitivity: tails of two distributions," in 31st Conference on Computational Complexity, Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern, 2016, vol. 50, p. 13.
    @INCOLLECTION{GSW,
      author = {Gopalan, Parikshit and Servedio, Rocco A. and Wigderson, Avi},
      title = {Degree and sensitivity: tails of two distributions},
      booktitle = {31st {C}onference on {C}omputational {C}omplexity},
      series = {LIPIcs. Leibniz Int. Proc. Inform.},
      volume = {50},
      pages = {Art. No. 13, 23},
      publisher = {Schloss Dagstuhl. Leibniz-Zent. Inform., Wadern},
      year = {2016},
      mrclass = {94D05 (68R10 94C10)},
      mrnumber = {3540814},
      mrreviewer = {Udrea P\u{a}un},
      zblnumber = {1380.68223},
      doi = {10.4230/LIPIcs.CCC.2016.13},
      url = {https://doi.org/10.4230/LIPIcs.CCC.2016.13},
     }
  • [gotsman-linial] Go to document C. Gotsman and N. Linial, "The equivalence of two problems on the cube," J. Combin. Theory Ser. A, vol. 61, iss. 1, pp. 142-146, 1992.
    @ARTICLE{gotsman-linial,
      author = {Gotsman, C. and Linial, N.},
      title = {The equivalence of two problems on the cube},
      journal = {J. Combin. Theory Ser. A},
      fjournal = {Journal of Combinatorial Theory. Series A},
      volume = {61},
      year = {1992},
      number = {1},
      pages = {142--146},
      issn = {0097-3165},
      mrclass = {05C35},
      mrnumber = {1178392},
      doi = {10.1016/0097-3165(92)90060-8},
      url = {https://doi.org/10.1016/0097-3165(92)90060-8},
      zblnumber = {0769.05050},
      }
  • [survey] Go to document P. Hatami, R. Kulkarni, and D. Pankratov, "Variations on the Sensitivity Conjecture," Theory of Computing Library, Graduate Surveys, vol. 4, pp. 1-27, 2011.
    @ARTICLE{survey,
      author = {Hatami, P. and Kulkarni, R. and Pankratov, D.},
      title = {Variations on the Sensitivity Conjecture},
      journal = {Theory of Computing Library, Graduate Surveys},
      volume = {4},
      year = {2011},
      pages = {1--27},
      zblnumber = {},
      url = {https://doi.org/10.4086/toc.gs.2011.004},
      doi = {10.4086/toc.gs.2011.004},
      }
  • [kenyon-kutin] Go to document C. Kenyon and S. Kutin, "Sensitivity, block sensitivity, and $l$-block sensitivity of Boolean functions," Inform. and Comput., vol. 189, iss. 1, pp. 43-53, 2004.
    @ARTICLE{kenyon-kutin,
      author = {Kenyon, Claire and Kutin, Samuel},
      title = {Sensitivity, block sensitivity, and {$l$}-block sensitivity of {B}oolean functions},
      journal = {Inform. and Comput.},
      fjournal = {Information and Computation},
      volume = {189},
      year = {2004},
      number = {1},
      pages = {43--53},
      issn = {0890-5401},
      mrclass = {68Q25 (06E30 94C10)},
      mrnumber = {2031916},
      mrreviewer = {Bruce Edward Litow},
      doi = {10.1016/j.ic.2002.12.001},
      url = {https://doi.org/10.1016/j.ic.2002.12.001},
      zblnumber = {1072.68047},
      }
  • [nisan] Go to document N. Nisan, "CREW PRAMs and decision trees," in Proc. 21st STOC, ACM Press, New York, 1989, pp. 327-335.
    @INCOLLECTION{nisan,
      author = {Nisan, N.},
      title = {{CREW PRAM}s and decision trees},
      booktitle = {Proc. 21st STOC},
      publisher = {ACM Press, New York},
      year = {1989},
      pages = {327--335},
      zblnumber = {},
      url = {https://doi.org/10.1145/73007.73038},
      doi = {10.1145/73007.73038},
      }
  • [nisan-szegedy] Go to document N. Nisan and M. Szegedy, "On the degree of Boolean functions as real polynomials," in Special Issue on Circuit Complexity, , 1994, vol. 4, pp. 301-313.
    @INCOLLECTION{nisan-szegedy,
      author = {Nisan, Noam and Szegedy, M\'{a}rió},
      title = {On the degree of {B}oolean functions as real polynomials},
      booktitle = {Special Issue on Circuit Complexity},
      venue = {Barbados, 1992},
      series = {Comput. Complexity},
      volume = {4},
      year = {1994},
      pages = {301--313},
      issn = {1016-3328},
      mrclass = {68Q25 (06E30 94C10)},
      mrnumber = {1313531},
      mrreviewer = {Nicolae \c{T}\u{a}nd\u{a}reanu},
      doi = {10.1007/BF01263419},
      url = {https://doi.org/10.1007/BF01263419},
      zblnumber = {0829.68047},
      }
  • [rubinstein] Go to document D. Rubinstein, "Sensitivity vs. block sensitivity of Boolean functions," Combinatorica, vol. 15, iss. 2, pp. 297-299, 1995.
    @ARTICLE{rubinstein,
      author = {Rubinstein, David},
      title = {Sensitivity vs. block sensitivity of {B}oolean functions},
      journal = {Combinatorica},
      fjournal = {Combinatorica. An International Journal on Combinatorics and the Theory of Computing},
      volume = {15},
      year = {1995},
      number = {2},
      pages = {297--299},
      issn = {0209-9683},
      mrclass = {68Q25 (94C10)},
      mrnumber = {1337360},
      doi = {10.1007/BF01200762},
      url = {https://doi.org/10.1007/BF01200762},
      zblnumber = {0837.68080},
      }
  • [tal] Go to document A. Tal, "Properties and applications of Boolean function composition," in ITCS’13—Proceedings of the 2013 ACM Conference on Innovations in Theoretical Computer Science, 2013, pp. 441-454.
    @INPROCEEDINGS{tal,
      author = {Tal, Avishay},
      title = {Properties and applications of {B}oolean function composition},
      booktitle = {I{TCS}'13---{P}roceedings of the 2013 {ACM} {C}onference on {I}nnovations in {T}heoretical {C}omputer {S}cience},
      pages = {441--454},
      publisher = {ACM, New York},
      year = {2013},
      mrclass = {94D05},
      mrnumber = {3385417},
      zblnumber = {1361.68094},
      doi = {10.1145/2422436.2422485},
     }
  • [virza] Go to document M. Virza, "Sensitivity versus black sensitivity of Boolean functions," Inform. Process. Lett., vol. 111, iss. 9, pp. 433-435, 2011.
    @ARTICLE{virza,
      author = {Virza, Madars},
      title = {Sensitivity versus black sensitivity of {B}oolean functions},
      journal = {Inform. Process. Lett.},
      fjournal = {Information Processing Letters},
      volume = {111},
      year = {2011},
      number = {9},
      pages = {433--435},
      issn = {0020-0190},
      mrclass = {06E30 (68Q15)},
      mrnumber = {2797276},
      doi = {10.1016/j.ipl.2011.02.001},
      url = {https://doi.org/10.1016/j.ipl.2011.02.001},
      zblnumber = {1260.68163},
      }

Authors

Hao Huang

Emory University, Atlanta, GA