OP-12047OpenComputational complexity

The degree--sensitivity exponent ( $C_{37}$ )

The degree--sensitivity exponent: determine $C_{37}$ or improve its bounds; the repository records $\log_{3}(6) \approx 1.63093$ (lower) and 2 (upper).

MSC 06E30 · Boolean functions

Editorial MSC2020 classification. Original article codes and source evidence are recorded in the literature directory.

Licensed source statementAs of Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differSource & evidence ↓

Read original source ↗ 0 Submit progress Lean 4 ↓Discussion (0)

Problem statement

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

Lean 4

Not yet attached

No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.

Share a formalization →Verification guide ↗

Background

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$ achieved 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].

References (from the repository page)

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

Progress & source assessment

Repository table (commit 2c1968c, 26 September 2026): best known lower bound $\log_{3}(6) \approx 1.63093$ ; best known upper bound 2. Values marked with an asterisk have minimal verification.

Known upper bounds

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$ ).

Known lower bounds

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

References

[1]Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — The degree--sensitivity exponent ($C_{37}$) linkApache-2.0 (repository license); constant pages reproduced with attribution; repository references retained.

Recorded progress

Add yours →

Nothing recorded yet. A pointer to a paper the entry is missing counts.

Machine attempts

0 recorded

Attempts run against the statement below and are recorded in full, including the failures. The point is to stop the next model — and the next person — from re-walking a road that is already known to end. Each attempt costs 25 credits.

No machine attempts recorded.

Discussion

0 notes

Notes are for clarifying the statement, flagging a missing reference, or recording why an approach fails. Claimed solutions belong in a submission, where they can be reviewed.

No notes yet.

Source & evidence

https://teorth.github.io/optimizationproblems/constants/37a.html

Constant page from github.com/teorth/optimizationproblems at commit 2c1968c, Apache-2.0. The maintainers review submissions for plausibility and replicability but do not certify correctness; asterisked bounds have minimal verification.

Source date: Repository table at commit 2c1968c (2026-09-26); open while the recorded lower and upper bounds differ
Imported: 2026-10-10

How we use sources ↗

Record

Difficulty: HardResisted sustained effort by specialists.
Posed by: Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers) and contributors
Posed: 2026
Source: Curated problem listOptimization Constants in Mathematics — Davis, Ivanisvili & TaoOptimization Constants in Mathematics — Davis, Ivanisvili & TaoOriginal statement ↗
Citation: Davis, Damek; Ivanisvili, Paata; Tao, Terence (maintainers). Optimization Constants in Mathematics, github.com/teorth/optimizationproblems (commit 2c1968c, 26 September 2026). — The degree--sensitivity exponent ($C_{37}$)
Added: 5 Nov 2026
Views: 0

Fields

Computational complexity