Sensitivity versus Degree for Boolean Multilinear Polynomials
Sensitivity versus Degree for Boolean Multilinear Polynomials. Solid result problem from Epoch AI’s FrontierMath: Open Problems; answers are checked by a verifier program.
Epoch field label “Combinatorics” mapped to MSC2020 06E30 for Sensitivity versus Degree for Boolean Multilinear Polynomials. https://epoch.ai/frontiermath/open-problems/degree-sensitivity-boolean Not an author-supplied code.
Problem statement
Given a Boolean function , it is known that the sensitivity of , denoted , is at least the square root of its degree, denoted , and that this bound is tight.
The upper bound is less clear. It is known that , with recent work improving this by a constant . There is also an explicit construction with . Here the exponent is .
The goal of this problem is to find a novel construction that improves on this bound.
Read more here.
Lean 4
No Lean statement or proof is attached yet. Have a formalization? Share its source to add it to this problem.
Background
FrontierMath: Open Problems lists this problem with notability “Solid result”, field “Combinatorics” and type “Construction - Finite; Improved Bound”. Each problem has a bespoke verifier program, so a proposed answer can be checked automatically.
Verifiable task — Epoch prompt, verbatim
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
Progress & source assessment
Epoch lists this problem as unsolved in its data archive updated 7 October 2026. Earlier AI attempts are not displayed by Epoch.
- [1]Epoch AI, ‘FrontierMath: Open Problems’. Published online at epoch.ai. Retrieved from https://epoch.ai/frontiermath/open-problems (data updated 7 October 2026). — Sensitivity versus Degree for Boolean Multilinear Polynomials linkCC BY 4.0 (Epoch AI data and problem pages); attributed reproduction of problem descriptions and verbatim task prompts.
Recorded progress
Add yours →Nothing recorded yet. A pointer to a paper the entry is missing counts.
Machine attempts
0 recordedAttempts 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.
Sign in to run an attempt. New accounts start with enough credits for ten.
Discussion
0 notesNotes 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.
Sign in to add a note.