The degree–sensitivity exponent

Description of constant

Let $f$ be a Boolean function on $n$ bits, i.e.

$f : {0, 1}^{n} \to {0, 1}$

with $n \geq 2$ . For $x \in$ {0,1}^n and $1 \leq i \leq n$ , let $x^{(i)}$ be $x$ with the $i$ -th bit flipped.

The (pointwise) sensitivity of $f$ at $x$ is

$s (f) (x) := i = 1 \sum n ∣ f (x) - f (x^{(i)}) ∣,$

and the (max) sensitivity is

$s (f) := x \in {0, 1}^{n} max s (f) (x) .$

Let $de g (f)$ be the degree of the unique multilinear polynomial over $R^{n}$ that agrees with $f$ on {0,1}^n.

Define the degree--sensitivity exponent

$C_{37} := sup \frac{lo g ( s ( f ))}{lo g ( de g ( f ))},$

where the supremum ranges over all $n \geq 2$ and all Boolean functions $f$ on {0,1}^n with $de g (f) > 1$ .

Equivalently, $C_{37}$ is the supremum over exponents $α > 0$ such that there exists a Boolean function $f$ of degree at least 2 with

$s (f) \geq (de g (f))^{α} .$

Known upper bounds

Bound	Reference	Comments
$2$	[NS1994], [T2013]	One has $s (f) \leq b s (f)$ and $b s (f) \leq O (de g (f)^{2})$ , giving an exponent upper bound $C_{37} \leq 2$ .
$2$	[P2021]	Improves the constant factor in the quadratic bound: $b s (f) \leq de g (f)^{2} / (10 - 2)$ , hence $s (f) \leq de g (f)^{2} / (10 - 2) \approx 0.8604 de g (f)^{2}$ (still exponent $2$ ).

Known lower bounds

Bound	Reference	Comments
$1$	Trivial	Parity on $n$ bits has $s (f) = n$ and $de g (f) = n$ .
$lo g_{2} 3 \approx 1.58496$	[BdW2002], [T2013]	Earlier explicit separation (pre-Kushilevitz)
$lo g_{3} 6 \approx 1.63093$	[HKP2011]	Kushilevitz function $h$ on $6$ bits has $s (h) = 6$ and $de g (h) = 3$ , and hence exponent $lo g_{3} 6$ .

Additional comments and links

The best known explicit exponent separating sensitivity from degree is currently $lo g_{3} 6$ (the “Kushilevitz barrier”). Improving this exponent is an open problem. “Kushilevitz function” was introduced (unpublished by Kushilevitz) in Footnote 1 of Nisan and Wigderson’s paper [NW95].

(Kushilevitz function.) One explicit polynomial representing the Kushilevitz function

$h : {0, 1}^{6} \to {0, 1}$ is $h (z_{1}, \dots, z_{6}) = \sum_{i = 1}^{6} z_{i} - \sum_{1 \leq i < j \leq 6} z_{i} z_{j} + (z_{1} z_{3} z_{4} + z_{1} z_{2} z_{5} + z_{1} z_{4} z_{5} + z_{2} z_{3} z_{4} + z_{2} z_{3} z_{5} + z_{1} z_{2} z_{6} + z_{1} z_{3} z_{6} + z_{2} z_{4} z_{6} + z_{3} z_{5} z_{6} + z_{4} z_{5} z_{6}),$

which is Boolean on {0,1}^6, has degree $3$ , and max sensitivity $s (f) = 6$ achieved at $x = (0, 0, 0, 0, 0, 0)$ .

Before Kushilevitz’s 6-variable function (giving exponent $lo g_{3} 6$ ), a simpler 3-variable function already yields exponent $lo g_{2} 3$ . One concrete choice is the "not-all-equal" function on 3 bits,

$g (x_{1}, x_{2}, x_{3}) = x_{1} + x_{2} + x_{3} - x_{1} x_{2} - x_{1} x_{3} - x_{2} x_{3},$

which is Boolean on the cube, has $de g (g) = 2$ , and $s (g) = 3$ at $x = (0, 0, 0)$ .

For background on the general relationship between sensitivity, block sensitivity, and degree (including Huang’s proof of the Sensitivity Conjecture), see [H2019] and the surveys [BdW2002], [HKP2011].

References

[BdW2002] Buhrman, H.; de Wolf, R. Complexity Measures and Decision Tree Complexity: A Survey. Theoretical Computer Science 288 (2002), 21–43. doi:10.1016/S0304-3975(01)00144-X.
[H2019] Huang, H. Induced Subgraphs of Hypercubes and a Proof of the Sensitivity Conjecture. Annals of Mathematics 190 (2019), 949–955. doi:10.4007/annals.2019.190.3.6.
[HKP2011] Hatami, P.; Kulkarni, R.; Pankratov, D. Variations on the Sensitivity Conjecture. Theory of Computing Library, Graduate Surveys 4 (2011). See Example 5.4 for Kushilevitz’s function and its powering. https://theoryofcomputing.org/articles/gs004/gs004.pdf
[NS1994] Nisan, N.; Szegedy, M. On the Degree of Boolean Functions as Real Polynomials. Computational Complexity 4 (1994), 301–313. doi:10.1007/BF01263419.
[NW95] Nisan, Noam; Wigderson, Avi. On rank vs. communication complexity. Combinatorica 15 (1995), no. 4, 557–565. Contains Footnote 1 describing Kushilevitz’s function. :contentReference[oaicite:2]{index=2}
[P2021] Proskurin, N. V. On Separation between the Degree of a Boolean Function and the Block Sensitivity. arXiv:2101.08600 (2021). https://arxiv.org/abs/2101.08600
[T2013] Tal, A. Properties and Applications of Boolean Function Composition. ITCS 2013, 441–454. doi:10.1145/2422436.2422485.

What counts as progress

A better upper or lower bound, with a proof or a construction whose value is re-computed by published code (reproducible), ideally with a certificate a deterministic checker can validate.
A formal proof (Lean) of a known bound, or a precise error in a claimed one.
New references for the tables above (literature claims).

Source and licence

Imported from the crowdsourced repository of optimization constants (Terence Tao and contributors), commit 2c1968cd520b, Apache License 2.0; reformatted for this page. New records should also be reported there.

Current state

The problem