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]
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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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] 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},
}
Full Article