# Average sensitivity of polynomial threshold functions > Yes-or-no rules built from degree-d polynomials on n inputs have average sensitivity at most 8d√n. Plain-English explainer, Lean status and sources. Canonical: https://closedform.nishachay.tech/e/openai-math-2026-127/ Last updated: 2026-10-11 **Yes-or-no rules built from degree-d polynomials on n inputs have average sensitivity at most 8d√n.** **Trust:** Formal proof listed · **Papers:** 1 · **First paper:** September 25, 2026 · **Field:** Theoretical computer science · **Entry:** 127 *Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error. Many yes-or-no rules work by computing a polynomial of the inputs and reading off its sign. Average sensitivity counts how many single inputs, on average, could flip the answer by changing alone. This paper proves that for a polynomial of degree d in n inputs, that count is at most 8d√n. This settles the asymptotic form of a conjecture that Gotsman and Linial posed in 1994. ## At a glance - **First step:** 1994 (Gotsman and Linial, proposed an exact bound) - **Significance:** Major. It closes the asymptotic form of a 1994 conjecture, removing the extra factors left by Kane's 2014 bound. - **Trust:** Formal proof listed - **Field:** Theoretical computer science (1 paper) ## The explanation Three people vote yes or no, and the majority wins. Write yes as +1 and no as −1. There are 8 equally likely ways the votes can fall. In 2 of them the vote is unanimous, and no single voter can change the result. In the other 6 the split is 2 to 1. Then either voter on the winning side could flip the result alone. So on average 6 × 2 / 8 = 1.5 voters are decisive. That average is called the average sensitivity of the rule. It is also called its total influence. Majority is the simplest polynomial threshold function. Such a rule computes a polynomial of the votes and outputs its sign. Majority uses x₁ + x₂ + x₃, a polynomial of degree 1. A polynomial of degree d may multiply up to d votes together in one term. Here the sign of exactly zero counts as +1. The paper allows any real coefficients, with no extra conditions[1]. How sensitive can such a rule be? With n voters, at most n can be decisive, so n is a trivial ceiling. Majority stays far below it. With 101 voters its average sensitivity is about 8.04. With 10,001 voters it is about 79.8. Both are close to 0.8 times √n. The new theorem says every rule of degree at most d has average sensitivity at most 8d√n[2]. For degree 1 and 10,001 voters, that ceiling is about 800. The shape d√n cannot be improved. The paper recalls symmetric rules, built from the count of yes votes, that reach that order. This holds whenever d is at most √n[3]. Only the constant 8 could still move. The question is old. In 1994 Gotsman and Linial proposed an exact bound. They named one symmetric rule as the most sensitive of all degree-d rules. Chapman later built counterexamples to that exact claim. He also separated it from a weaker asymptotic form: sensitivity at most a constant times d√n[4]. That weaker form is what this paper addresses[5]. Kim, Maldonado and Wellens independently found counterexamples for degree 2. Early general bounds grew more slowly than n for each fixed degree. Harsha, Klivans and Meka proved one. Diakonikolas, Raghavendra, Servedio and Tan proved another independently. Both first circulated in 2009 and appeared in journals in 2014. In 2014 Kane reached the right power of n, the square root. His bound still carried extra factors that grow with log n and very fast with d. The obstacle lay in how those proofs worked. They compared the voting cube with smooth bell-curve random inputs[6]. That comparison only works for regular polynomials, where no single vote matters too much. The other cases had to be cut down to regular ones, and each step cost a factor. This paper uses no such comparison. Its proof pairs a short probability fact with a construction of matrices on the cube itself[7]. That route removes the extra factors and leaves a bound linear in d[8]. Back to the voters. Take any degree-1 rule on 10,001 votes, with any weights and threshold. On average it has at most about 800 decisive voters. Any degree-2 rule has at most about 1,600. The degree may even grow with the number of voters[9]. But the bound beats the trivial ceiling only when 8d√n is below n. For 10,001 voters that means degree 12 or less. The theorem also assumes every pattern of votes is equally likely. It says nothing about which rule is exactly the most sensitive[10]. The paper also derives two side results from the main bound[11]. One controls noise sensitivity, how often random flips of many votes change the answer. The other is a guarantee for learning such rules from labeled examples. How sure is this? A computer proof checker called Lean has checked a formal version of the main theorem. It covers the bound 8d√n for every degree, every n, and the convention that zero counts as +1. The noise and learning results are outside that check. No specialist review has been published yet. **What it doesn't show.** This does not say which rule is exactly the most sensitive, or that the constant 8 is best. ## Where it came from This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026. ## Hype check Major if it holds up. Lean has checked the main bound, but the side results are not machine-checked. No specialist review has been published, and the exact extremal question stays open. ## Words used - **Boolean cube:** The set of all lists of n entries, each +1 or −1, like every possible pattern of n yes-or-no votes. - **Polynomial threshold function:** A yes-or-no rule that computes a polynomial of the inputs and outputs its sign, counting zero as +1. - **Degree:** The largest number of inputs multiplied together in any single term of the polynomial. - **Average sensitivity (total influence):** The average number of inputs that could each flip the rule's answer by changing alone, over all equally likely inputs. - **Regular polynomial:** A polynomial in which no single input carries too large a share of the weight. - **Noise sensitivity:** The chance that the answer changes when each input is flipped independently with a small probability. ## The original paper - [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf) - September 25, 2026 · Formal proof listed - [Lean notes](https://github.com/openai/math/blob/main/lean/docs/127.md) ## Quoted lines from the paper (11) [1] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > The polynomial may vanish on the cube, and no regularity condition is imposed on $p$. [2] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > For every $n\ge1$ and $1\le d\le n$, we prove that a polynomial threshold function of degree at most $d$ on the uniform Boolean cube has average sensitivity at most $8d\sqrt n$. This proves the asymptotic form of the Gotsman--Linial conjecture. [3] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > Thus the order $d\sqrt n$ is sharp throughout this degree range; see also. [4] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > Chapman constructed counterexamples to this exact assertion and explicitly distinguished it from the asymptotic bound $I(f)=O(d\sqrt n)$. [5] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > This proves the asymptotic form of the Gotsman--Linial conjecture. [6] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > Their proofs use regularity and invariance arguments to compare sufficiently regular Boolean polynomials with Gaussian ones. [7] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > The proof separates a probability estimate from a finite-dimensional operator construction. [8] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > His proof combines random restrictions, regularity, and invariance estimates. Theorem … removes that loss and gives linear dependence on $d$ with an absolute constant. [9] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > In particular, the degree may grow with the dimension. [10] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > Theorem … establishes the asymptotic bound with an absolute constant; it makes no assertion about exact maximizers. [11] From [Average sensitivity of polynomial threshold functions](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): > Section … derives a dimension-free Boolean noise sensitivity bound and a quantitative learning guarantee from the influence estimate. ## Other sources - [OpenAI, “Average sensitivity of polynomial threshold functions”, openai/math preprint (25 September 2026)](https://github.com/openai/math/blob/main/preprints/Average-Sensitivity-of-Polynomial-Threshold-Functions-September-25-2026/main.pdf): “This proves the asymptotic form of the Gotsman--Linial conjecture.” - [C. Gotsman and N. Linial, “Spectral properties of threshold functions”, Combinatorica 14 (1994), 35–50](https://doi.org/10.1007/BF01305949) - [B. Chapman, “The Gotsman–Linial conjecture is false”, SODA 2018, 692–699](https://doi.org/10.1137/1.9781611975031.45) - [H. W. Kim, C. Maldonado and J. Wellens, “On graphs and the Gotsman–Linial conjecture for d=2”, arXiv:1709.06650 (2017)](https://arxiv.org/abs/1709.06650v1) - [P. Harsha, A. Klivans and R. Meka, “Bounding the sensitivity of polynomial threshold functions”, Theory of Computing 10 (2014), 1–26](https://doi.org/10.4086/toc.2014.v010a001) - [I. Diakonikolas, P. Raghavendra, R. A. Servedio and L.-Y. Tan, “Average sensitivity and noise sensitivity of polynomial threshold functions”, SIAM Journal on Computing 43 (2014), 231–253](https://doi.org/10.1137/110855223) - [D. M. Kane, “The correct exponent for the Gotsman–Linial conjecture”, Computational Complexity 23 (2014), 151–175](https://doi.org/10.1007/s00037-014-0086-z) ## Related - [Exponential semidefinite complexity of perfect matching](https://closedform.nishachay.tech/e/openai-math-2026-126/) - Theoretical computer science - [Rapid mixing of graph switches for every degree sequence](https://closedform.nishachay.tech/e/openai-math-2026-131/) - Theoretical computer science - [A superquadratic separation of sensitivity and block sensitivity](https://closedform.nishachay.tech/e/openai-math-2026-132/) - Theoretical computer science - [Homogeneous depth-five lower bounds for iterated matrix multiplication](https://closedform.nishachay.tech/e/openai-math-2026-135/) - Theoretical computer science - [Bin packing and unbounded configuration-LP gaps](https://closedform.nishachay.tech/e/openai-math-2026-118/) - Theoretical computer science - [Theoretical computer science](https://closedform.nishachay.tech/science/mathematics/theoretical-computer-science/) - Field · 40 results - [Open since the 1990s](https://closedform.nishachay.tech/open-since/1990s/) - Era · 55 results - [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results - [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20127%5D%20)