change the value of . Sensitivity is related to the notion of total influence from the analysis of Boolean functions, which is equal to average sensitivity over all . The sensitivity conjecture is the conjecture that sensitivity is polynomially related to query complexity; that is, there exists exponent such that, for all , and . One can show through a simple argument that , so the conjecture is specifically concerned about finding a lower bound for sensitivity. Since all of the previously-discussed complexity measures are polynomially related, the precise type of complexity measure is not relevant. However, this is typically phrased as the question of relating sensitivity with block sensitivity. The block sensitivity of , denoted , is defined to be the maximum block sensitivity of over all . The block sensitivity of at is the maximum number of disjoint subsets such that, for any of the subsets , flipping the bits of corresponding to changes the value of . Since block sensitivity takes a maximum over more choices of subsets, . Further, block sensitivity is polynomially related to the previously discussed complexity measures; for example, Nisan's paper introducing block-sensitivity showed that . So, one could rephrase the sensitivity conjecture as showing that, for some , . In 1992, Nisan and Szegedy conjectured that suffices. This would be tight, as Rubinstein in 1995 showed a quadratic separation between sensitivity and block sensitivity. In July 2019, 27 years after the conjecture was initially posed, Hao Huang from Emory University proved the sensitivity conjecture, showing that . This proof is notably succinct, proving this statement in two pages when prior progress towards the sensitivity conjecture had been limited. Summary of known results This table summarizes results on separations between Boolean function complexity measures. The complexity measures are, in order, deterministic, zero-error randomized, two-sided-error randomized, certificate, randomized certificate, block sensitivity, sensitivity, exact quantum, degree, quantum, and approximate degree complexities. The number in the -th row and -th column denotes bounds on the exponent , which is the infimum of all satisfying for all boolean functions . For example, the entry in the D-th row and s-th column is "3, 6", so for all , and there exists a function such that . See also Comparison sort Decision tree Aanderaa–Karp–Rosenberg conjecture Minimum spanning tree#Decision trees References Surveys Computational complexity theory Models of computation Decision trees