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.
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.
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.
Number of mathematicians highly familiar with the problem:
a majority of those working on a specialized topic (≈10)
Number 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%