1 Introduction
A polynomial threshold function assigns a sign to each vertex of the Boolean cube by evaluating a real polynomial. On the cube, the identities x_i^2=1 allow every polynomial to be replaced by a multilinear polynomial of no larger degree without changing its values. Average sensitivity measures the expected number of coordinate changes that reverse that sign. For x\in\{-1,1\}^n, let x^{\oplus i} be obtained by reversing coordinate i. For f:\{-1,1\}^n\to\{-1,1\}, define
This quantity is also called the total influence of f. Throughout,
We prove the following estimate.
Theorem 1. Let n\ge1 and 1\le d\le n be integers. Let p be a real multilinear polynomial of degree at most d, and define f:\{-1,1\}^n\to\{-1,1\} by f(x)=\sgn(p(x)), with \sgn(0)=1. Then, for average sensitivity under the uniform law,
The constant is independent of both d and n. In particular, the degree may grow with the dimension. The polynomial may vanish on the cube, and no regularity condition is imposed on p.
Gotsman and Linial proposed an exact extremal bound for average sensitivity [4, Section 5, p. 47]. Their candidate is symmetric: it is the sign of a degree-d polynomial in x_1+\cdots+x_n whose roots lie between the central levels of the cube. The proposal asserts that this function maximizes influence among all degree-d polynomial threshold functions in n variables. Chapman constructed counterexamples to this exact assertion and explicitly distinguished it from the asymptotic bound I(f)=O(d\sqrt n) [2, Conjectures 1.1–1.2 and Theorem 1.1]. Kim, Maldonado, and Wellens independently constructed quadratic counterexamples for odd n\ge5 and proved influence bounds for quadratic polynomials with restricted support graphs [9, Theorems 1.1–1.3]. Theorem 1 establishes the asymptotic bound with an absolute constant; it makes no assertion about exact maximizers. Numbered locators in references with a listed preprint refer to that preprint version.
The classical symmetric examples explain the scale of the theorem. Let 1\le d\le\sqrt n, let J consist of the d indices nearest (n-1)/2 in \{0,\ldots,n-1\}, breaking a tie arbitrarily, and put
Here t(x) is the number of coordinates of x equal to +1. Multilinearization preserves the values of p_J on the cube and has degree at most d. Its sign changes exactly across the boundaries between Hamming weights j and j+1 for j\in J. There are (n-j)\binom nj=n\binom{n-1}j unoriented edges at such a boundary, so the ordered-edge normalization in (1) gives
Here the comparison constants are absolute. The central-binomial estimate from Stirling’s formula, together with the ratios of consecutive binomial coefficients, shows that the binomial masses are comparable to n^{-1/2} within \sqrt n/2 of the center, which includes all selected indices; the case n=1 follows directly from the count. Thus the order d\sqrt n is sharp throughout this degree range; see also [9, p. 3, discussion following Theorem 1.1]. For every Boolean function, the additional bound I(f)\le n holds.
Early general bounds established sublinear influence for every fixed degree. For n>1, Harsha, Klivans, and Meka proved I(f)\le2^{O(d)}n^{1-1/(4d+6)} [5, Theorem 1.6], while the independent work of Diakonikolas, Raghavendra, Servedio, and Tan gave I(f)\le2^{O(d)}(\log n)n^{1-1/(4d+2)} [3, Theorem 1.1]. These results first circulated in 2009, before their 2014 journal publications. Their proofs use regularity and invariance arguments to compare sufficiently regular Boolean polynomials with Gaussian ones. Kane subsequently established the square-root exponent in the dimension:
[8, Theorem 2]. For each fixed d\ge2, this is an n^{1/2+o(1)} bound with a polylogarithmic loss. His proof combines random restrictions, regularity, and invariance estimates. Theorem 1 removes that loss and gives linear dependence on d with an absolute constant.
Small moments of the local sensitivity s_f(x)=|\{i:f(x)\ne f(x^{\oplus i})\}| give further information about its distribution. Chang, Slote, Volberg, and Zhang bounded the Boolean surface area \E\sqrt{s_f(X)} by a polynomial in \log(en) for each fixed degree [1, Theorem 1.1, equation (1.6)]. Tseng and Volberg studied a wider range of sensitivity moments [11]. For comparison with the first moment, the pointwise inequality s_f\le\sqrt n\sqrt{s_f} converts the surface-area estimate into an influence bound with a logarithmic loss. At moment order one, the estimate in [11, Section 2.5, equation (11)] is C(d)\sqrt n(\log n)^{Cd\log d} for n>1, which likewise retains a logarithmic factor for d\ge2.
Proof strategy. The proof separates a probability estimate from a finite-dimensional operator construction. The probability estimate says that equal-law random variables of variance \sigma^2 satisfy \E(U-V)^2\le8a\sigma whenever V-U\le a almost surely. A bound on increments in the opposite direction is not assumed. Equality of the marginal laws supplies the needed balance through an increasing function whose increments dominate squared displacement. Section 2 proves this estimate directly.
For the operator construction, begin with the spaces of cube polynomials of degrees at most k, for 0\le k\le n. Multiply these spaces by \sqrt w for a positive weight w, and take their successive orthogonal increments in the counting inner product. The increments have dimensions \binom nk, although the weight changes their positions. Give the kth increment eigenvalue k-n/2; this defines a self-adjoint operator M with fixed squared Hilbert–Schmidt norm n2^n/4. Its squared Hilbert–Schmidt norm is the sum of the squared moduli of all matrix entries. Multiplication by a coordinate connects only equal or adjacent grades, because it raises polynomial degree by at most one and is self-adjoint. These are the two features of the grading used in the proof: fixed dimensions and locality under coordinate multiplication (Section 3).
When w\equiv1, M is minus one-half of the cube adjacency matrix. For a general weight, some edge entries may have smaller squared modulus, and other entries may appear. Section 4 shows that the total squared entry mass between vertices at distance at least two is bounded by the mass on the diagonal. Together with a bound on each edge entry, this controls the total deficit from the unweighted squared edge value 1/4. If H multiplies by a sign function h, the anticommutator MH+HM retains diagonal entries and equal-sign edge entries, multiplying them by 2 or -2. Its squared norm therefore bounds the number of equal-sign edges even for an arbitrary positive weight.
Finally, multiply f by full parity to obtain h(x)=(\prod_{i=1}^n x_i)f(x), and use w=|p| after removing zeros without changing signs. The equal-sign edges of h are exactly the sensitive edges of f. Moreover, multiplication by parity turns the Fourier support of p into degrees at least n-d. This forces the block of H between grades r and s to vanish when r+s<n-d. The normalized squared block norms define a probability law for (R,S) whose two marginals are \operatorname{Bin}(n,1/2). Reflecting one index gives U=S and V=n-R, with the same marginals and V-U\le d. The coupling estimate then bounds the anticommutator norm, and the edge estimate gives the theorem. Section 5 performs this assembly, keeping track of ordered edges.
Consequences. Section 6 derives a dimension-free Boolean noise sensitivity bound and a quantitative learning guarantee from the influence estimate. The learning statement concerns independent labeled samples whose input marginal is uniform, while the labels may be arbitrary. It follows by combining noise smoothing with polynomial regression.
2 A one-sided coupling estimate
The next lemma controls mean square displacement from an upper bound in only one direction. Large downward displacements are permitted, so bounding the positive and negative displacements separately would lose information. Equality of the marginal laws instead balances the expected change of any integrable function applied to the two variables. We use an increasing function whose increments dominate squared displacement; its increments in the bounded direction can be estimated using the common variance. Neither independence nor exchangeability is assumed.
Lemma 2. Let U,V be real random variables with the same distribution, finite mean m, and finite variance \sigma^2. If V-U\le a almost surely, where a\ge0, then
Proof. The function |t-m| grows linearly away from the common mean. Its primitive is the increasing function
For u<v, we have
For the lower bound, if u\le m\le v, the integral is \bigl((m-u)^2+(v-m)^2\bigr)/2\ge(v-u)^2/4; if the interval lies on one side of m, the integral is at least (v-u)^2/2. For the upper bound, convexity places \abs{z-m} below the chord joining its endpoint values, whose integral is the displayed upper bound.
The second-moment assumption makes g(U) and g(V) integrable. Their expectations agree. For the integrable random variable Y=g(V)-g(U), write Y_+=\max\{Y,0\}. The identity \E Y=0 implies \E|Y|=2\E Y_+. Since g is strictly increasing, Y>0 exactly when V>U, and hence
The first inequality uses (3) and V-U\le a on \{V>U\}; the last is Cauchy–Schwarz. The lower bound in (3), with the endpoints put in increasing order, gives (U-V)^2\le4|g(U)-g(V)| pointwise. Taking expectations proves the lemma.
The cancellation \E[g(V)-g(U)]=0 uses only equality of marginal laws. Primitive differences with this property also appear in Röllin’s formulation of Stein’s method [10, Section 1]. The present one-sided second-moment estimate follows from the elementary increment bounds above.
3 Weighted Fourier grading
We next construct an operator whose spectrum is fixed by the dimensions of polynomial spaces, while its matrix entries respond to an arbitrary positive weight. The construction is the cube instance of the usual degree filtration for discrete multivariate orthogonal polynomials, whose coordinate multipliers satisfy a three-term recurrence; compare Xu [12, Section 3]. We give the finite-dimensional argument in the present notation.
Write \Omega=\{-1,1\}^n and N=2^n. We work in \mathcal H=\mathbb C^\Omega with the counting inner product
Thus the point masses \delta_x form an orthonormal basis. For an operator B, write B_{xy}=\ip{\delta_x}{B\delta_y} and let
be its Hilbert–Schmidt norm squared; \norm B_{\op} denotes its operator norm. The Hilbert–Schmidt norm is independent of the orthonormal basis.
For S\subseteq[n]=\{1,\ldots,n\}, set \chi_S(x)=\prod_{j\in S}x_j. These real characters satisfy
Indeed, a nonconstant character sums to zero by pairing vertices that differ in one of its coordinates. The displayed product rule therefore gives orthogonality, and the N characters form a basis of the N-dimensional space \mathcal H. Let
and set V_k=\mathcal H for k\ge n. Membership in V_k means that a function has Fourier degree at most k. The character multiplication rule shows that a\in V_r and b\in V_s imply \overline b a\in V_{r+s}.
Fix any function w:\Omega\to(0,\infty), and let D be multiplication by \sqrt w. The identity
identifies the weighted inner product with the counting inner product after applying D. We can therefore orthogonalize polynomial degrees for the weight w while retaining the orthonormal point basis used to count edges. Form the nested subspaces
Let \Pi_k be the orthogonal projection onto E_k. The spaces K_k are nested, and K_k=K_{k-1}\oplus E_k. Since D is invertible, \dim K_k=\dim V_k=\sum_{j=0}^k\binom nj and K_n=\mathcal H. Subtracting consecutive dimensions gives
Choosing an orthonormal basis in each E_k and decomposing the image of each basis vector gives, for every operator B,
Define the grading operator and its centered version by
They are self-adjoint. Their prescribed eigenvalue multiplicities give
The last equality is the variance identity for a sum of n independent Bernoulli random variables of parameter 1/2.
Let \rho(x,y) denote Hamming distance. All pairs of vertices in what follows are ordered. When w\equiv1, the identity \sum_{y:\rho(x,y)=1}\chi_S(y)=(n-2\abs S)\chi_S(x) shows that M is minus one-half of the cube adjacency matrix. Thus every edge entry has squared modulus 1/4; the proof below controls the total deficit from this value for arbitrary positive weights.
The key local property is that multiplying by a coordinate connects only equal or adjacent grades.
For each i\in[n], let Z_i be multiplication by x_i. It is a self-adjoint unitary and commutes with D. Multiplication by x_i raises Fourier degree by at most one, so Z_iK_r\subseteq K_{r+1}. For s>r+1, the inclusion K_{r+1}\subseteq K_{s-1} and the orthogonality E_s\perp K_{s-1} give \Pi_sZ_i\Pi_r=0. Taking adjoints gives the opposite triangular vanishing, so
Together with the fixed total energy in (6), this restriction will control the entries of M between vertices at Hamming distance at least two.
4 Recovering edges from the anticommutator
Keep the grading of Section 3, with no restriction on the positive weight w. For an operator H that multiplies by a sign, the anticommutator MH+HM vanishes between opposite signs and multiplies entries of M by 2 or -2 between equal signs. The following lemma turns this observation into an edge count even though an arbitrary weight can change the individual edge entries.
Lemma 3 (Recovering edges from the grading). Let n\ge1, \Omega=\{-1,1\}^n, and w:\Omega\to(0,\infty). Let M be the centered grading operator (5) constructed from w. For h:\Omega\to\{-1,1\}, let H be multiplication by h and set
Then, counting ordered pairs,
Proof. We compare M with the unweighted grading, whose edge entries have squared modulus 1/4. First we show that every edge entry of M has squared modulus at most 1/4. We then bound the sum of the deficits by diagonal energy, which the anticommutator detects for every choice of signs.
A bound for each off-diagonal entry. Write C_i=[L,Z_i]=[M,Z_i], where [A,B]=AB-BA. Its grade blocks are
We will prove \norm{C_i}_{\op}\le1. The commutator keeps only adjacent-grade blocks, with opposite signs in the two directions. We first remove the equal-grade blocks by a norm-nonincreasing average, then supply those opposite signs, up to a common phase, by unitary conjugation. Introduce the unitaries
Set O_i=(Z_i-JZ_iJ)/2. The triangle inequality gives \norm{O_i}_{\op}\le(\norm{Z_i}_{\op}+\norm{JZ_iJ}_{\op})/2=1. In the (s,r) block, the factor defining O_i is (1-(-1)^{s+r})/2. It is zero on the diagonal and one when |s-r|=1. By (7), O_i therefore consists precisely of the blocks of Z_i with \abs{s-r}=1. On these blocks, conjugation by W multiplies by \mathrm i^{s-r}=\mathrm i(s-r). Therefore
In the point basis, (C_i)_{xy}=(y_i-x_i)M_{xy}. If x\ne y, choose i with x_i\ne y_i to obtain
In particular, each neighbor deficit 1/4-\abs{M_{xy}}^2 is nonnegative.
The total neighbor deficit. The same grade blocks also give an aggregate bound. By (4) and (7),
Summing the squared point-basis entries of C_i over coordinates gives
where the last equality is (6). Set
The difference between the outermost sums in (9) is -A_0+\sum_{\rho(x,y)\ge2}(\rho(x,y)-1)|M_{xy}|^2\le0. Thus energy beyond neighboring pairs is bounded by diagonal energy:
There are nN ordered neighbor pairs, and thus
Here we used (6) and (10). The fixed total energy consequently controls the full deficit from the unweighted edge value 1/4.
Recovering the equal-sign edges. Let A_h=\sum_{(x,y)\in\mathcal E_h}\abs{M_{xy}}^2. Because the individual deficits are nonnegative, their sum over \mathcal E_h is at most the full sum in (11). Hence
For T=MH+HM we have T_{xy}=(h(x)+h(y))M_{xy}. On both the diagonal and \mathcal E_h, the squared factor is 4, so
5 Parity and the binomial coupling
We now choose the weight from the polynomial. Parity will convert the sensitivity problem into the equal-sign edge count of Lemma 3, while the polynomial degree will produce the one-sided constraint needed for Lemma 2.
Proof of Theorem 1.
We may assume that p(x)\ne0 for every x\in\Omega. Indeed, if p takes negative values, add a positive constant smaller than \min\{\abs{p(x)}:p(x)<0\}; otherwise add any positive constant. Negative values remain negative, while zero values become positive and positive values stay positive. Thus the perturbation preserves f under our convention \sgn(0)=1, does not increase the degree, and makes p nonzero at every vertex. We henceforth use p for the perturbed polynomial.
Let \chi=\chi_{[n]} be full parity and set
Full parity changes sign across every edge, so h(x)=h(y) for neighbors x,y exactly when f(x)\ne f(y). Consequently
Here both sides count sensitive edges in both directions. We have w>0 and hw=q. Construct the weighted grading (5) from w, and let H be multiplication by h. Since \chi\chi_S=\chi_{[n]\setminus S} and \deg p\le d, the Fourier support of q lies in degrees at least n-d.
We claim that
To see this, write elements of E_r\subseteq DV_r and E_s\subseteq DV_s as Da and Db, with a\in V_r and b\in V_s. Then
The last equality follows from character orthogonality: the product \overline b a has Fourier degree at most r+s<n-d.
Set T=MH+HM. Its blocks are
Thus the anticommutator energy is a weighted second moment of the sum of the two grade indices:
The coefficients on the right define a probability distribution. Indeed, because H is unitary and the projections are orthogonal,
Decomposing the domain into grades and taking adjoints likewise gives
Since \sum_r\binom nr=N, we may therefore define random indices R,S\in\{0,\ldots,n\} by
Both marginals are \operatorname{Bin}(n,1/2), and the preceding energy identity becomes
To use Lemma 2, reflect the first index: put U=S and V=n-R. Binomial symmetry gives U and V the same distribution, with mean n/2 and variance n/4. Meanwhile, (14) gives R+S\ge n-d almost surely, which becomes V-U\le d. Figure 1 shows how the zero-block region becomes this one-sided support constraint.
Figure 1: Grade blocks and their reflected coupling, schematic for 0<d<n. Under U=S, V=n-R, the zero-block region r+s<n-d becomes the zero-mass region v-u>d, giving V-U\le d almost surely. Dashed boundaries are allowed; solid diagonals mark r+s-n=u-v=0. Each marginal is \operatorname{Bin}(n,1/2). Unshaded locations need not carry positive mass, and grid spacing is illustrative.
Apply Lemma 2 with a=d and \sigma=\sqrt n/2 to obtain
Finally, (13) and Lemma 3 give
This completes the proof.
6 Noise sensitivity and agnostic learning
The influence bound has two consequences that are independent of the weighted grading used to prove it. A random-bucketing construction transfers the bound from one-bit changes to independent noise. Smoothing by this noise then gives low-degree polynomial approximants, which yield an agnostic learner by L_1 regression.
6.1 Noise sensitivity
For 0\le\eta\le1/2, define the noise sensitivity \operatorname{NS}_{\eta}(f)=\Prb\{f(X)\ne f(Y)\}, where X is uniform on the cube and Y is obtained by flipping each coordinate of X independently with probability \eta.
Corollary 4 (Boolean noise sensitivity). Let n\ge1 and d\ge0 be integers. If f=\sgn(p) on \{-1,1\}^n for a real polynomial p of degree at most d, with \sgn(0)=1, then
where C is an absolute constant.
Proof. Constants have zero noise sensitivity. For an integer q\ge2, use the random-bucketing reduction of Diakonikolas, Raghavendra, Servedio, and Tan [3, Section 7.1, equation (14)]: choose independent uniform signs a_i and independent uniform buckets b(i)\in\{1,\ldots,q\}, and set
Multilinearizing the substituted polynomial preserves its cube values, including zeros, and gives degree at most \min(d,q). Theorem 1 therefore gives I(g)\le8d\sqrt q; a constant substitution contributes zero.
Independently choose uniform z\in\{-1,1\}^q and J\in\{1,\ldots,q\}. Put X_i=a_i z_{b(i)} and Y_i=X_i(-1)^{\mathbf1_{\{b(i)=J\}}}. Conditional on J, the flip indicators are independent Bernoulli variables of parameter 1/q, and their joint law does not depend on J. Conditional on b,J,z, the random signs make X uniform, so X is independent of the flip vector. Thus (X,Y) has exactly the noise law at rate 1/q. Since replacing z by z^{\oplus J} produces Y, averaging first over z,J gives
For the rest of this section, Fourier coefficients and L_1,L_2 norms are normalized by uniform probability on the cube. In particular, \widehat f(S)=\E[f(X)\chi_S(X)] and
This expression is nondecreasing for 0\le\eta\le1/2. Taking q=\lfloor1/\eta\rfloor, so that \eta\le1/q\le1/2 and q\ge1/(2\eta), proves the claim with C=8\sqrt2.
For comparison, Kane proved an absolute O(d\sqrt\varepsilon) noise sensitivity bound for degree-d polynomial threshold functions under standard Gaussian noise [7, Theorem 1]. Here 0<\varepsilon\le1, and the input pair is X and (1-\varepsilon)X+\sqrt{2\varepsilon-\varepsilon^2}\,Z, with X,Z independent standard Gaussian vectors. His proof counts sign changes along Gaussian rotations. Corollary 4 gives the same dependence on degree and noise rate for independent coordinate flips on the Boolean cube.
6.2 Agnostic learning
In agnostic learning the labels may be arbitrary: the objective is to predict nearly as well as the best function in a specified class. We use the L_1 polynomial regression method of Kalai, Klivans, Mansour, and Servedio [6], which was applied to polynomial threshold functions in [3, Section 8].
Corollary 5 (Uniform-marginal agnostic learning). Let n,d\ge1 be integers, and let \mathcal C_{n,d} be the class of functions \sgn(p) on \{-1,1\}^n with \deg p\le d. Let D be any distribution on \{-1,1\}^n\times\{-1,1\} whose first marginal is uniform, and set
There is an absolute constant A such that, for 0<\alpha,\delta<1, a learner using independent labeled samples from D returns, with probability at least 1-\delta, a Boolean hypothesis h satisfying
Its running time and sample size are polynomial in (n+1)^k, 1/\alpha, and \log(1/\delta), where
The labels are unrestricted, and h need not belong to \mathcal C_{n,d}.
Proof. We first construct an L_1 approximant to each f\in\mathcal C_{n,d}. For 0<\eta<1/2 and \rho=1-2\eta, the noise operator is
Equivalently, T_\rho f(x) is the expected value of f after independent noise of rate \eta is applied to x. Since f is Boolean and T_\rho f takes values in [-1,1], |f-T_\rho f|=1-fT_\rho f pointwise. Corollary 4 therefore gives, with C=8\sqrt2,
Take \eta=(\alpha/(8Cd))^2 and K=\lceil\log(4/\alpha)/(2\eta)\rceil. Let q be the Fourier truncation of T_\rho f to degrees at most \min(K,n). If K<n, Parseval’s identity gives
if K\ge n, the truncation error is zero. The first error is also at most \alpha/4, so
Taking A=32C^2 makes \min(K,n)=k in the statement.
For completeness, we explain how this direct L_1 estimate enters the regression argument of [6, proof of Theorem 5]. Use the M=\sum_{j=0}^k\binom nj\le(n+1)^k characters of degree at most k as features. On a training sample Z of size m, fit a polynomial P in these features by minimizing empirical absolute loss, then choose t\in[-1,1] to minimize the empirical error of h=\sgn(P-t). The fit is a linear program, and the threshold is found by sorting the fitted values. Write \widehat{\E}_Z and \widehat{\operatorname{err}}_Z for empirical means and errors. A uniformly random threshold has error at most half the absolute loss, so the minimizing threshold satisfies
Choose an optimal f\in\mathcal C_{n,d} and its fixed approximant q. The triangle inequality and (18) imply \E_Z\widehat{\operatorname{err}}_Z(h)\le\mathrm{OPT}+\alpha/4. These hypotheses are halfspaces in the M character features, so their VC dimension is at most M+1. The usual expected uniform generalization bound, as used in [6, proof of Theorem 5], makes \E_Z\operatorname{err}_D(h)\le\mathrm{OPT}+3\alpha/8 for m polynomial in M and 1/\alpha.
Apply Markov’s inequality to the nonnegative random variable \operatorname{err}_D(h). Since \mathrm{OPT}\le1 and \alpha<1,
Thus one trial succeeds with probability at least \alpha/12. Repeat independently r=\lceil(12/\alpha)\log(2/\delta)\rceil times. With probability at least 1-\delta/2, one candidate has this error. On an independent validation sample of size \lceil8\alpha^{-2}\log(4r/\delta)\rceil, Hoeffding’s inequality and a union bound estimate all r errors within \alpha/4, except with probability \delta/2. Selecting the best validation score therefore gives error at most \mathrm{OPT}+\alpha. All the training, regression, repetition and validation costs have the stated polynomial bounds.
References
- [1]Fan Chang, Joseph Slote, Alexander Volberg, and Haonan Zhang, The Boolean surface area of polynomial threshold functions, preprint, 2026. arXiv:2604.08095v2.
- [2]Brynmor Chapman, The Gotsman–Linial conjecture is false, in Proceedings of the Twenty-Ninth Annual ACM–SIAM Symposium on Discrete Algorithms (SODA 2018), Society for Industrial and Applied Mathematics, 2018, 692–699.
doi:10.1137/1.9781611975031.45. Preprint: arXiv:2108.02288v1. - [3]Ilias Diakonikolas, Prasad Raghavendra, Rocco A. Servedio, and Li-Yang Tan, Average sensitivity and noise sensitivity of polynomial threshold functions, SIAM Journal on Computing 43 (2014), no. 1, 231–253.
doi:10.1137/110855223. Preprint: arXiv:0909.5011v2. - [4]Craig Gotsman and Nathan Linial, Spectral properties of threshold functions, Combinatorica 14 (1994), no. 1, 35–50.
doi:10.1007/BF01305949. - [5]Prahladh Harsha, Adam Klivans, and Raghu Meka, Bounding the sensitivity of polynomial threshold functions, Theory of Computing 10 (2014), no. 1, 1–26.
doi:10.4086/toc.2014.v010a001. - [6]Adam Tauman Kalai, Adam R. Klivans, Yishay Mansour, and Rocco A. Servedio, Agnostically learning halfspaces, SIAM Journal on Computing 37 (2008), no. 6, 1777–1805.
doi:10.1137/060649057. - [7]Daniel M. Kane, The Gaussian surface area and noise sensitivity of degree-d polynomial threshold functions, Computational Complexity 20 (2011), 389–412.
doi:10.1007/s00037-011-0012-6. Preprint (titled The Gaussian surface area and noise sensitivity of degree-d polynomials): arXiv:0912.2709v1. - [8]Daniel M. Kane, The correct exponent for the Gotsman–Linial conjecture, Computational Complexity 23 (2014), no. 2, 151–175.
doi:10.1007/s00037-014-0086-z. Preprint: arXiv:1210.1283v1. - [9]H. W. Kim, C. Maldonado, and J. Wellens, On graphs and the Gotsman–Linial conjecture for d=2, preprint, 2017. arXiv:1709.06650v1.
- [10]Adrian Röllin, A note on the exchangeability condition in Stein’s method, Statistics & Probability Letters 78 (2008), no. 13, 1800–1806.
doi:10.1016/j.spl.2008.01.043. Preprint: arXiv:math/0611050v2. - [11]Chun-Kai Tseng and Alexander Volberg, Small moments of the sensitivity of polynomial threshold functions, preprint, 2026. arXiv:2606.16004v2.
- [12]Yuan Xu, On discrete orthogonal polynomials of several variables, Advances in Applied Mathematics 33 (2004), 615–632.
doi:10.1016/j.aam.2004.03.002. Preprint: arXiv:math/0401418v2.