Degree vs Sensitivity for Boolean Functions

Improve the exponent in the upper bound that degree has over sensitivity.

Notability: Solid result

Solved: No

Field: Combinatorics

On this page:

About the problem Attempts by AI AI prompts Mathematician survey

About the problem

Given a Boolean function $f$, it is known that the sensitivity of $f$, denoted $s(f)$, is at least the square root of its degree, denoted $\deg(f)$, and that this bound is tight.

The upper bound is less clear. It is known that $s(f) \le \bigl(\deg(f)\bigr)^2$, with recent work improving this by a constant $< 1 (\approx 0.83)$. There is also an explicit construction with $s(f) = \bigl( \deg(f) \bigr)^{\log(6)/\log(3)}$. Here the exponent is $\approx 1.63$.

The goal of this problem is to find a novel construction that improves on this bound.

Warm-up: we ask for the current best known lower bound.

Full write-up

Attempts by AI

We have evaluated the following models on this problem. “Warm-up” refers to an easier variant of the problem with a known solution.

Model

Problem

Solved

Logs

GPT-5.2 Pro

Warm-up

Yes

GPT-5.2 Pro

Full Problem

Gemini 3 Deep Think

Full Problem

AI Prompts

Warm-up

Construct a multilinear, integer-coefficient function P, on n variables, with 1 < n ≤ 100, with degree deg(P) > 1, that is Boolean on the cube, i.e., P(x) = 0 or 1 for all x in {0,1 }^n, and that has

|P(0, ..., 0) - P(1, 0, ..., 0)| + |P(0, ..., 0) - P(0, 1, 0, ..., 0)| + ... + |P(0, ..., 0) - P(0, ..., 0, 1)| = deg(P)^a

for some a > 1.63.

Provide your answer as an expression using variables like x1, x2, etc. For operators use +, -, and *. You may also use parentheses. Example: x1 + x2 + x3 - (x1*x2 + x1*x3 + x2*x3) + x1*x2*x3

Full problem

Construct a multilinear, integer-coefficient function P, on n variables, with 1 < n ≤ 100, with degree deg(P) > 1, that is Boolean on the cube, i.e., P(x) = 0 or 1 for all x in {0,1 }^n, and that has

|P(0, ..., 0) - P(1, 0, ..., 0)| + |P(0, ..., 0) - P(0, 1, 0, ..., 0)| + ... + |P(0, ..., 0) - P(0, ..., 0, 1)| = deg(P)^a

for some a > log(6)/log(3).

Provide your answer as an expression using variables like x1, x2, etc. For operators use +, -, and *. You may also use parentheses. Example: x1 + x2 + x3 - (x1*x2 + x1*x3 + x2*x3) + x1*x2*x3

Mathematician survey

The author assessed the problem as follows.

# of mathematicians highly familiar with the problem: a majority of those working on a specialized topic (≈10)

# of mathematicians who have made a serious attempt to solve the problem: 5–10

Rough guess of how long it would take an expert human to solve the problem: 1–4 weeks

Notability of a solution: a solid result in a subfield

A solution would be published: in a standard specialty journal

Likelihood of a solution generating more interesting math: somewhat likely: an especially innovative solution could, but is hardly guaranteed

Probability that the problem is solvable as stated: 40-60%