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\ge 2$. For $x\in$ {0,1}^n and $1\le i\le n$, let $x^{(i)}$ be $x$ with the $i$-th bit flipped.

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

\[s(f)(x):=\sum_{i=1}^n |f(x)-f(x^{(i)})|,\]

and the (max) sensitivity is

\[s(f):=\max_{x\in\{0,1\}^n} s(f)(x).\]

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

Define the degree–sensitivity exponent

\[C_{37}:=\sup \frac{\log \ (s(f))}{\log (\deg(f))},\]

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

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

\[s(f)\ge (\deg(f))^{\alpha}.\]

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

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

The best known explicit exponent separating sensitivity from degree is currently $\log_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\le i<j\le 6} z_i z_j + (z_1z_3z_4 + z_1z_2z_5 + z_1z_4z_5 + z_2z_3z_4 + z_2z_3z_5 + z_1z_2z_6 + z_1z_3z_6 + z_2z_4z_6 + z_3z_5z_6 + z_4z_5z_6),$

which is Boolean on {0,1}^6, has degree $3$, and max sensitivity $s(f)=6$ achieving at $x=(0,0,0,0,0,0)$.
Before Kushilevitz’s 6-variable function (giving exponent $\log_3 6$), a simpler 3-variable function already yields exponent $\log_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_1x_2-x_1x_3-x_2x_3,$

which is Boolean on the cube, has $\deg(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].

[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.