Average sensitivity of polynomial threshold functions

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 conditionsSource 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√nSource 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 √nSource 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√nSource 4. That weaker form is what this paper addressesSource 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 inputsSource 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 itselfSource 7. That route removes the extra factors and leaves a bound linear in dSource 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 votersSource 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 sensitiveSource 10.

The paper also derives two side results from the main boundSource 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.