On the resolution of the sensitivity conjecture

Karthikeyan, Rohan; Sinha, Siddharth; Patil, Vallabh

doi:10.1090/bull/1697

On the resolution of the sensitivity conjecture
HTML articles powered by AMS MathViewer

by Rohan Karthikeyan, Siddharth Sinha and Vallabh Patil HTML | PDF

Bull. Amer. Math. Soc. 57 (2020), 615-638 Request permission

Abstract:

The sensitivity conjecture is a long-standing problem in theoretical computer science that seeks to fit the sensitivity of a Boolean function into a unified framework formed by the other complexity measures of Boolean functions, such as block sensitivity and certificate complexity. After more than thirty years of attacks on this conjecture, Hao Huang (2019) gave a very succinct proof of the conjecture. In this survey, we explore the ideas that inspired the proof of this conjecture by an exposition of four papers that had the most impact on the conjecture. We also discuss progress on further research directions that the conjecture leads us to.

References

C. Gotsman and N. Linial, The equivalence of two problems on the cube, J. Combin. Theory Ser. A 61 (1992), no. 1, 142–146. MR 1178392, DOI 10.1016/0097-3165(92)90060-8
F. R. K. Chung, Zoltán Füredi, R. L. Graham, and P. Seymour, On induced subgraphs of the cube, J. Combin. Theory Ser. A 49 (1988), no. 1, 180–187. MR 957216, DOI 10.1016/0097-3165(88)90034-9
Noam Nisan and Márió Szegedy, On the degree of Boolean functions as real polynomials, Comput. Complexity 4 (1994), no. 4, 301–313. Special issue on circuit complexity (Barbados, 1992). MR 1313531, DOI 10.1007/BF01263419
Hao Huang, Induced subgraphs of hypercubes and a proof of the sensitivity conjecture, Ann. of Math. (2) 190 (2019), no. 3, 949–955. MR 4024566, DOI 10.4007/annals.2019.190.3.6
Ryan O’Donnell, Some topics in analysis of Boolean functions, STOC’08, ACM, New York, 2008, pp. 569–578. MR 2582688, DOI 10.1145/1374376.1374458
Noam Nisan, CREW PRAMs and decision trees, SIAM J. Comput. 20 (1991), no. 6, 999–1007. MR 1135744, DOI 10.1137/0220062
J. Kahn, G. Kalai, N. Linial. The influence of variables on boolean functions. FOCS (1988), 68-80.
Stephen Cook, Cynthia Dwork, and Rüdiger Reischuk, Upper and lower time bounds for parallel random access machines without simultaneous writes, SIAM J. Comput. 15 (1986), no. 1, 87–97. MR 822194, DOI 10.1137/0215006
Harry Buhrman and Ronald de Wolf, Complexity measures and decision tree complexity: a survey, Theoret. Comput. Sci. 288 (2002), no. 1, 21–43. Complexity and logic (Vienna, 1998). MR 1934888, DOI 10.1016/S0304-3975(01)00144-X
P. Hatami, R. Kulkarni, D. Pankratov. Variations on the Sensitivity Conjecture. Theory of Computing Library, Graduate Surveys 4 (2011), 1–27.
David Rubinstein, Sensitivity vs. block sensitivity of Boolean functions, Combinatorica 15 (1995), no. 2, 297–299. MR 1337360, DOI 10.1007/BF01200762
S. Fisk. A very short proof of Cauchy’s interlace theorem for eigenvalues of Hermitian matrices. Amer. Math. Monthly, 112 (2) (2005), 118.
Y. Gu, X.-L. Qi. Majorana fermions and the Sensitivity Conjecture, arXiv:1908.06322 (2019).
M. Szegedy. Algebraic methods in Lower Bounds for Computational Models with Limited Communication. Ph. D. thesis, University of Chicago, 1989.
R. Gray. Graphs with a high degree of symmetry (PowerPoint slides). Available at: https://archive.uea.ac.uk/~fga12juu. (2007)
R. A. Bailey. Distance-transitive graphs. M. Math dissertation, University of Leeds, 2002.
H. D. Macpherson, Infinite distance transitive graphs of finite valency, Combinatorica 2 (1982), no. 1, 63–69. MR 671146, DOI 10.1007/BF02579282
A. Gardiner, Homogeneous graphs, J. Combinatorial Theory Ser. B 20 (1976), no. 1, 94–102. MR 419293, DOI 10.1016/0095-8956(76)90072-1
R. Rado, Universal graphs and universal functions, Acta Arith. 9 (1964), 331–340. MR 172268, DOI 10.4064/aa-9-4-331-340
A. Gardiner, Homogeneity conditions in graphs, J. Combin. Theory Ser. B 24 (1978), no. 3, 301–310. MR 496449, DOI 10.1016/0095-8956(78)90048-5
R. Gray and D. Macpherson, Countable connected-homogeneous graphs, J. Combin. Theory Ser. B 100 (2010), no. 2, 97–118. MR 2595694, DOI 10.1016/j.jctb.2009.04.002
D. Dong. On induced subgraphs of the Hamming graph, arXiv:1912.01780 (2019).
Geir Agnarsson, Induced subgraphs of hypercubes, European J. Combin. 34 (2013), no. 2, 155–168. MR 2994391, DOI 10.1016/j.ejc.2012.09.004
A. Ambainis, X. Sun. New separation between $s(f)$ and $bs(f)$, Electronic Colloquium on Computational Complexity (ECCC), 18 (116) (2011).
Daniel V. Mathews. The sensitivity conjecture, induced subgraphs of cubes, and Clifford algebras, arXiv:1907.12357 (2019).
A. Tikaradze. Induced subgraphs of powers of oriented cycles, arXiv:1908.10463 (2019).
Aleksei Shadrin, Twelve proofs of the Markov inequality, Approximation theory: a volume dedicated to Borislav Bojanov, Prof. M. Drinov Acad. Publ. House, Sofia, 2004, pp. 233–298. MR 2117091
Stasys Jukna, Boolean function complexity, Algorithms and Combinatorics, vol. 27, Springer, Heidelberg, 2012. Advances and frontiers. MR 2895965, DOI 10.1007/978-3-642-24508-4
Q. I. Rahman and G. Schmeisser, Analytic theory of polynomials, London Mathematical Society Monographs. New Series, vol. 26, The Clarendon Press, Oxford University Press, Oxford, 2002. MR 1954841
K. Regan, Gödel’s lost letter and $P=NP$, Tools and Sensitivity, July 2019.
E, Klarreich, Decades-old computer science conjecture solved in two pages, Quanta Magazine, July 2019.