Polynomial threshold functions: how often can one flipped bit change a decision?

← All digests

Family 127 · Theoretical computer science
Importance 3/5 · Provisional editorial rating
Sources consulted 2026-10-09

1. The question

A decision rule reads $n$ binary inputs, evaluates a polynomial, and returns its sign. How unstable can that decision be under a single changed input?

For a majority vote, changing one vote matters only when the original vote is near a tie. For parity, which asks whether the number of negative inputs is even or odd, every single change reverses the answer. These examples suggest that the algebraic complexity of a rule should constrain its average sensitivity to perturbations.

Polynomial threshold functions formalize this question. The degree limits how many variables can interact in one polynomial term, while thresholding converts the polynomial’s numerical output to a yes/no decision. A low-degree polynomial can have arbitrary real coefficients and a complicated zero set, so bounding the boundary of its sign pattern is not a simple counting exercise.

This manuscript claims that every degree-$d$ polynomial threshold function on the uniform Boolean cube has average sensitivity at most $8d\sqrt n$. It identifies this as a resolution of the asymptotic Gotsman–Linial conjecture. The original conjecture about exact extremizers is different and already has counterexamples.

2. Background and essential definitions

The Boolean cube is the set $\{-1,1\}^n$. Two vertices are neighbors if they differ in exactly one coordinate. For a vertex $x$, write $x^{\oplus i}$ for the result of reversing coordinate $i$.

A polynomial threshold function has the form

$$f(x)=\operatorname{sgn}(p(x)), \qquad \operatorname{sgn}(t)= \begin{cases} 1,&t\ge0,\\ -1,&t<0. \end{cases}$$

The convention at zero is part of the theorem. Since $x_i^2=1$ on the cube, powers of a variable can be reduced to obtain a multilinear polynomial without changing values or increasing degree. “Multilinear” means that each variable has exponent at most one in every term.

The sensitivity at $x$ counts neighbors with a different answer. Averaging over a uniformly random vertex $X$ gives total influence, another name for average sensitivity:

$$I(f)=\sum_{i=1}^n \Pr\bigl[f(X)\ne f(X^{\oplus i})\bigr].$$

This is an expected count, not a probability, and it can range from zero to $n$. Equivalently, it measures how many cube edges cross the boundary between the positive and negative decision regions, with a normalization by the number of vertices.

For majority with odd $n$, only inputs close to a tie contribute. A central-binomial estimate gives influence of order $\sqrt n$. Thus even a degree-one threshold can have a growing boundary. The proposed theorem scales this behavior linearly with the polynomial degree.

3. Development history and previous partial results

Gotsman and Linial’s 1994 paper proposed an exact extremal description. Their candidate functions depend only on the sum of the coordinates and change sign across selected central layers of the cube. For degree $d$, the conjecture identified a particular symmetric threshold as maximizing influence.

That exact assertion did not survive. Chapman constructed counterexamples and explicitly separated the exact conjecture from the weaker asymptotic prediction $I(f)=O(d\sqrt n)$. Kim, Maldonado, and Wellens independently obtained quadratic counterexamples and results for restricted polynomial support. Consequently, proving the asymptotic estimate would not revive the false exact-maximizer statement.

General bounds first established sublinear influence for every fixed degree. Harsha, Klivans, and Meka, and independently Diakonikolas, Raghavendra, Servedio, and Tan, used regularity and invariance methods. These compare suitable Boolean polynomials with Gaussian analogues after controlling unusually influential coordinates. Their bounds improved on the trivial $n$, but initially had an exponent above one half. See Harsha–Klivans–Meka and Diakonikolas and coauthors.

Kane then obtained the correct square-root exponent, with logarithmic losses depending on degree. For fixed $d$, this gave $n^{1/2+o(1)}$, rather than a constant times $d\sqrt n$. More recent work studied smaller moments of pointwise sensitivity and related notions of Boolean surface area. Those estimates illuminate the boundary’s distribution but do not automatically remove all losses in its first moment.

The claimed advance is therefore specific: remove the extra logarithmic factors and obtain an absolute constant with linear dependence on degree, uniformly even when $d$ grows with $n$.

4. What the new manuscripts claim

For every $n\ge1$, every integer $1\le d\le n$, and every real polynomial $p$ of degree at most $d$, the manuscript states

$$I(\operatorname{sgn}p)\le8d\sqrt n.$$

No regularity or nonvanishing assumption is imposed. Coefficients may be arbitrary real numbers, and zeros use the specified positive-sign convention. The constant eight is independent of both parameters.

Together with the elementary $I(f)\le n$, the useful bound is $\min\{n,8d\sqrt n\}$. For degrees well above $\sqrt n$, the trivial bound can be stronger. Symmetric examples show that the order $d\sqrt n$ cannot generally be improved when $d$ is at most on the order of $\sqrt n$. The manuscript does not claim that eight is the optimal leading constant.

A stated consequence concerns independent noise. If each coordinate is flipped with probability $\eta\in(0,1/2]$, the probability that the function changes satisfies

$$\operatorname{NS}_{\eta}(f)\le C d\sqrt\eta$$

for an absolute constant $C$, independent of dimension. This is a probability bound and can always be capped at one.

The paper also derives an agnostic-learning guarantee under uniformly distributed inputs. Labels can be arbitrary; the learner aims to come within additive error $\alpha$ of the best degree-$d$ threshold rule. Its sample and time bounds are polynomial in $(n+1)^k$, $1/\alpha$, and $\log(1/\delta)$, where

$$k=\min\left\{n,\left\lceil A d^2\alpha^{-2}\log(4/\alpha)\right\rceil\right\}$$

and $\delta$ is failure probability. The output hypothesis need not itself be a degree-$d$ threshold function. This is polynomial for fixed degree and accuracy, not jointly polynomial in all those parameters.

5. Why the advance matters

Provisional importance: 3/5. The claim settles a substantial sharp-order problem in the analysis of Boolean functions. It gives a clean relationship between algebraic degree and the average size of a decision boundary, with corresponding stability and learning consequences.

Uniformity in degree matters. A bound with a constant allowed to grow arbitrarily with $d$ can say little when degree changes with dimension. The stated linear dependence remains interpretable across the entire permitted range, even though it eventually meets the trivial ceiling.

The result also clarifies a useful distinction between average and worst-case behavior. A low-degree rule may be highly sensitive at specially chosen inputs while having a controlled average boundary. That distinction is important in learning theory and probabilistic analysis, but it is not a guarantee of robustness against every adversarially selected input.

The score reflects a strong contribution within Boolean analysis, with broader methodological connections, rather than a universal stability theorem for arbitrary data distributions or classifiers.

6. The main idea

Turn polynomial degree into an operator structure

The manuscript’s approach departs from simply transferring a Gaussian bound. It considers spaces of cube polynomials of degree at most $k$, for each $k$, and weights them using a positive function. Taking successive orthogonal differences produces graded subspaces: layers of functions indexed by degree.

Weighting changes these subspaces but preserves their dimensions. Multiplication by a coordinate can move a function only between nearby grades, because it increases polynomial degree by at most one. The proof builds a self-adjoint operator whose eigenvalue on grade $k$ is $k-n/2$.

With uniform weight this operator is closely related to the cube’s adjacency matrix. For a general positive weight, its entries are more complicated. The manuscript controls how much squared matrix mass can move away from cube edges and uses an anticommutator to count edges on which a sign function agrees. An anticommutator of operators $A,B$ is simply $AB+BA$.

Exchange disagreement for agreement

Multiply the threshold function by full parity,

$$h(x)=\left(\prod_{i=1}^n x_i\right)f(x).$$

Parity changes on every cube edge. Therefore an edge where $f$ changes sign is exactly an edge where $h$ keeps its sign. This converts the desired sensitive-edge count into the kind of agreement count controlled by the operator argument.

After handling zeros without changing the threshold’s values, the weight is chosen from $|p|$. Multiplication by parity shifts the polynomial’s Fourier support toward high degrees. That forces certain blocks of the sign-multiplication operator to vanish.

Use a one-sided probability constraint

The squared sizes of the remaining blocks define a joint distribution for two grade indices. Each marginal has a binomial distribution. Reflecting one index produces equal-law random variables $U,V$ satisfying a one-sided bound $V-U\le d$.

The key probability estimate says that if equal-law variables have variance $\sigma^2$ and $V-U\le a$, then

$$\mathbb E(U-V)^2\le8a\sigma.$$

The variables need not be independent. Equality of their marginal distributions balances the potentially large displacement in the other direction. Here the binomial standard deviation is $\sqrt n/2$, so the estimate naturally produces the product $d\sqrt n$. The operator comparison converts it back into an influence bound.

For noise sensitivity, the manuscript randomly groups coordinates and applies the influence estimate to the resulting lower-dimensional threshold function. Noise smoothing then yields low-degree polynomial approximations, which connect to established regression-based learning methods.

7. Scope, limitations, and open questions

The measure is uniform on the Boolean cube. Biased inputs, dependent coordinates, and arbitrary distributions require separate statements. The theorem is also about the sign of a degree-bounded polynomial; it does not bound arbitrary Boolean functions by a small $d$.

The asymptotic conjecture concerns order of growth, not an exact extremal function or best constant. Those finer questions remain distinct, especially because the original symmetric-extremizer conjecture is false.

Noise sensitivity measures random perturbations. An adversary choosing which coordinates to flip can behave differently. Likewise, the learning consequence assumes a uniform input marginal even though it permits arbitrary labels, and its degree and accuracy dependence can be large.

Finally, the argument’s operator and coupling estimates are reported as the manuscript’s method. The digest does not independently establish them. Their potential use for other boundary problems is a direction for further work, not an additional theorem supplied here.

8. Sources and further reading

The original Gotsman–Linial paper, Chapman’s counterexamples, and Kane’s square-root-exponent result locate the new claim precisely. The earlier sensitivity papers explain regularity and invariance approaches. The source manuscript below includes the weighted-operator construction, the noise consequence, and the stated uniform-marginal learning bound.

Source manuscripts

• M1. OpenAI, Average sensitivity of polynomial threshold functions (September 25, 2026).

Sources consulted on 9 October 2026 at repository revision fd4aeeb. Download the manuscript citations.