标题： 戈茨曼-林纳尔猜想是错误的 显示英文标题

标题： The Gotsman-Linial Conjecture is False

摘要： 1991年，Craig Gotsman和Nathan Linial猜想，对于所有$n$和$d$，关于$n$个变量的次数为$d$的多项式阈值函数的平均敏感性由次数为$d$的对称多项式最大化，该多项式在与$n/2$最接近的汉明重量的$d$层上计算奇偶函数。 我们否定了几乎所有$d$和几乎所有$n$的猜想，并在剩余情况中的许多情况下确认了该猜想。 显示英文摘要

摘要： In 1991, Craig Gotsman and Nathan Linial conjectured that for all $n$ and $d$, the average sensitivity of a degree-$d$ polynomial threshold function on $n$ variables is maximized by the degree-$d$ symmetric polynomial which computes the parity function on the $d$ layers of the hypercube with Hamming weight closest to $n/2$. We refute the conjecture for almost all $d$ and for almost all $n$, and we confirm the conjecture in many of the remaining cases.