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.
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.
a majority of those working on a specialized topic (≈10)
5–10
1–4 weeks
a solid result in a subfield
in a standard specialty journal
somewhat likely: an especially innovative solution could, but is hardly guaranteed
40-60%