Sensitivity theorem

In computational complexity, the Sensitivity Theorem, proved by Hao Huang in 2019, states that the sensitivity of a Boolean function $f\colon \{0,1\}^{n}\to \{0,1\}$ is at least the square root of its degree, thus settling a conjecture posed by Nisan and Szegedy in 1992.

Background

Several papers in the late 1980s and early 1990s showed that various decision tree complexity measures of Boolean functions are polynomially related, meaning that if $\alpha (f),\beta (f)$ are two such measures then $\alpha (f)\leq C\beta (f)^{C}$ for some constant $C>0$. Nisan and Szegedy showed that degree and approximate degree are also polynomially related to all these measures. Their proof went via yet another complexity measure, block sensitivity, which had been introduced by Nisan. Block sensitivity generalizes a more natural measure, (critical) sensitivity, which had appeared before.

Nisan and Szegedy asked whether block sensitivity is polynomially bounded by sensitivity (the other direction is immediate since sensitivity is at most block sensitivity). This is equivalent to asking whether sensitivity is polynomially related to the various decision tree complexity measures, as well as to degree, approximate degree, and other complexity measures which have been shown to be polynomially related to these along the years. This became known as the sensitivity conjecture.

Along the years, several special cases of the sensitivity conjecture were proven. The sensitivity theorem was finally proven in its entirety by Huang, using a reduction of Gotsman and Linial.

Statement

Every Boolean function $f\colon \{0,1\}^{n}\to \{0,1\}$ can be expressed in a unique way as a multilinear polynomial. The degree of $f$ is the degree of this unique polynomial, denoted $\deg(f)$.

The sensitivity of the Boolean function $f$ at the point $x\in \{0,1\}^{n}$ is the number of indices $i\in [n]$ such that $f(x^{\oplus i})\neq f(x)$, where $x^{\oplus i}$ is obtained from $x$ by flipping the $i$'th coordinate. The sensitivity of $f$ is the maximum sensitivity of $f$ at any point $x\in \{0,1\}^{n}$, denoted $s(f)$.

The sensitivity theorem states that

$s(f)\geq {\sqrt {\deg(f)}}.$

In the other direction, Tal, improving on an earlier bound of Nisan and Szegedy, showed that

$s(f)\leq \deg(f)^{2}.$

The sensitivity theorem is tight for the AND-of-ORs function:

$\bigwedge _{i=1}^{m}\bigvee _{j=1}^{m}x_{ij}$

This function has degree $m^{2}$ and sensitivity $m$.

See also

• Decision tree model

References

• Bafna, Mitali; Lokam, Satyanarayana V.; Tavenas, Sébastien; Velingker, Ameya; Faliszewski, Piotr; Muscholl, Anca; Niedermeier, Rolf (2016). "On the Sensitivity Conjecture for Read-k Formulas". 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). p. 14 pages. doi:10.4230/LIPICS.MFCS.2016.16. ISSN 1868-8969.
• Blum, Manuel; Impagliazzo, Russell (1987). "Generic oracles and oracle classes". 28th Annual Symposium on Foundations of Computer Science (sfcs 1987). IEEE. doi:10.1109/sfcs.1987.30.
• Buhrman, Harry; de Wolf, Ronald (2002). "Complexity measures and decision tree complexity: a survey". Theoretical Computer Science. 288 (1). Elsevier BV: 21–43. doi:10.1016/s0304-3975(01)00144-x. ISSN 0304-3975.
• C. S., Karthik; Tavenas, Sébastien; Lal, Akash; Akshay, S.; Saurabh, Saket; Sen, Sandeep (2016). "On the Sensitivity Conjecture for Disjunctive Normal Forms". 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2016). p. 15 pages. doi:10.4230/LIPICS.FSTTCS.2016.15. ISSN 1868-8969.
• Cook, Stephen; Dwork, Cynthia; Reischuk, Rüdiger (1986). "Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes". SIAM Journal on Computing. 15 (1): 87–97. doi:10.1137/0215006. ISSN 0097-5397.
• Gotsman, Chaim; Linial, Nati (1992). "The equivalence of two problems on the cube". Journal of Combinatorial Theory, Series A. 61 (1). Elsevier BV: 142–146. doi:10.1016/0097-3165(92)90060-8. ISSN 0097-3165.
• Hartmanis, Juris; Hemachandra, Lane A. (1991). "One-way functions and the nonisomorphism of NP-complete sets". Theoretical Computer Science. 81 (1): 155–163. doi:10.1016/0304-3975(91)90323-T.
• Hatami, Pooya; Kulkarni, Raghav; Pankratov, Denis (2011). "Variations on the Sensitivity Conjecture". Theory of Computing. 1 (1): 1–27. doi:10.4086/toc.gs.2011.004. ISSN 1557-2862.
• Huang, Hao (2019-11-01). "Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture". Annals of Mathematics. 190 (3). doi:10.4007/annals.2019.190.3.6. ISSN 0003-486X.
• Nisan, Noam (1991). "CREW PRAMs and Decision Trees". SIAM Journal on Computing. 20 (6): 999–1007. doi:10.1137/0220062. ISSN 0097-5397.
• Nisan, Noam; Szegedy, Mario (1994). "On the degree of boolean functions as real polynomials". Computational Complexity. 4 (4): 301–313. doi:10.1007/BF01263419. ISSN 1016-3328.
• Simon, Hans-Ulrich (1983). "A tight Ω(loglog n)-bound on the time for parallel Ram's to compute nondegenerated boolean functions". Foundations of Computation Theory. Vol. 158. Berlin, Heidelberg: Springer Berlin Heidelberg. doi:10.1007/3-540-12689-9_124. ISBN 978-3-540-12689-8.
• Tal, Avishay (2013-01-09). "Properties and applications of boolean function composition". ITCS '13: Proceedings of the 4th conference on Innovations in Theoretical Computer Science. ACM. doi:10.1145/2422436.2422485. ISBN 978-1-4503-1859-4.
• Tardos, G. (1989). "Query complexity, or why is it difficult to separate $NP^{A}\cap coNP^{A}$ from $P^{A}$ by random oracles $A$?". Combinatorica. 9 (4): 385–392. doi:10.1007/BF02125350. ISSN 0209-9683.
• Wegener, Ingo (1987). The Complexity of Boolean Functions. Stuttgart Chichester New York Brisbane [etc.]: John Wiley & Sons. ISBN 0-471-91555-6.