A compensated coupling bound for the average sensitivity of polynomial threshold functions

Technical Summary: A Compensated Coupling Bound for the Average Sensitivity of Polynomial Threshold Functions

Problem Statement
The paper addresses the problem of bounding the average sensitivity ($AS(f)$) of polynomial threshold functions (PTFs). A PTF is a Boolean function $f: \{-1, 1\}^n \to \{-1, 1\}$ defined as the sign of a real polynomial $p$ of degree at most $d$. The average sensitivity is defined as the expected number of input bits that, when flipped, change the function's output:
$$AS(f) = \sum_{i=1}^n P\{f(X) \neq f(X^{\oplus i})\}$$
where $X$ is uniform on the Boolean cube $\Omega_n$. While the Gotsman–Linial conjecture (identifying exact symmetric maximizers) has been shown to be false, the search for tight uniform upper bounds remains a central topic in Boolean function analysis and computational complexity. Previous work by OpenAI [1] established a bound of $8d\sqrt{n}$, and a prior note by the authors refined this to a uniform coefficient of 3.83.

Methodology
The authors refine the "weighted-grading" argument originally developed by OpenAI [1]. This approach reduces the estimation of average sensitivity to a coupling problem involving binomial random variables. The core methodological contributions of this paper are:

1. Compensated Coupling Estimate: The authors introduce a refined probabilistic lemma (Lemma 2) involving a "compensated coupling." This lemma bounds the second moment of the difference between two random variables ($U, V$) with identical distributions and a bounded displacement ($V - U \le a$). By introducing a linear correction to the coupling potential, the authors eliminate the degree-squared loss present in earlier bounds.
2. Finite-Range Estimation: The paper derives a finite-parameter estimate that accounts for the specific dimensions $n$ and degrees $d$, rather than relying solely on asymptotic approximations.
3. Binomial Coupling Construction: The authors construct specific binomial couplings to demonstrate the tightness of their relaxation. They show that the derived coefficient is asymptotically sharp for the specific relaxation that utilizes only the two marginal laws, the one-sided displacement constraint, and the existing factor-two grading comparison.

Key Results
The paper establishes two primary bounds for a real polynomial threshold function $f$ of degree $d$ on the $n$-dimensional Boolean cube:

1. Uniform Asymptotic Bound:
   $$AS(f) \le \frac{8}{\sqrt{2\pi}} d\sqrt{n} \approx 3.19 d\sqrt{n}$$
   This bound holds uniformly for all dimensions $n$ and degrees $d$.

2. Stronger Finite-Parameter Bound:
   $$AS(f) \le \min\left\{n, \frac{8 d b_n (n + d)}{n + 2d}\right\}$$
   where $b_n = E|B_n - n/2|$ for $B_n \sim \text{Bin}(n, 1/2)$. This formula explicitly captures the dependence on $n$ and $d$, showing that the coefficient decreases as $d$ increases relative to $n$.

The authors also prove that the coefficient $8/\sqrt{2\pi}$ cannot be improved by simply bounding the second moment over all couplings with binomial marginals and displacement constraints, establishing a barrier for this specific relaxation approach.

Claims and Significance
The paper positions its contribution as a sharpening of the probability step within the existing weighted-grading framework.

• Refinement: The work improves the uniform coefficient from the previous 3.83 to $8/\sqrt{2\pi}$.
• Uniformity: The new bound is valid uniformly across dimensions and degrees, including cases where the degree grows with the dimension.
• Limitations and Modesty: The authors explicitly state that they do not assert optimality for polynomial threshold functions themselves. They clarify that the constructed couplings demonstrating the sharpness of the coefficient may not arise from actual polynomial threshold functions. Furthermore, the paper does not claim to establish exhaustive historical priority, independent human peer review, or a formal Lean proof.
• Verification: The results are supported by analytic inequalities and extensive computational verification (checking over 12,000 pointwise inequalities and 8,000 dimension-degree pairs) using exact arithmetic and standard libraries, rather than floating-point approximations.

In summary, the paper provides a tighter, uniformly valid upper bound for the average sensitivity of PTFs by refining the coupling step in the weighted-grading argument, while carefully delineating the scope of its optimality claims regarding the specific relaxation used.