The Gotsman-Linial Conjecture is False

MaRDI QIDQ4607926zbMATH OpenFDO

Authors

Publication date 15 March 2018

Full work available at URL https://arxiv.org/abs/2108.02288, http://dl.acm.org/citation.cfm?id=3175315

Mathematics Subject Classification ID

Abstract: 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.

Recommendations

• scientific article; zbMATH DE number 653253
• Steinberg's conjecture is false
• scientific article; zbMATH DE number 5666686
• The strong simplex conjecture is false
• The Demyanov-Ryabova conjecture is false
• Hedetniemi's conjecture is asymptotically false
• The <scp>Gross–Saccoman</scp> conjecture is true
• Inverse conjecture for the Gowers norm is false
• Inverse conjecture for the Gowers norm is false
• The permanent-on-top conjecture is false

Cited in

(6)

• Geometric and o-minimal Littlewood-Offord problems
• Proving the conjecture of O'Donnell in certain cases and disproving its general validity
• scientific article; zbMATH DE number 5666686 (Why is no real title available?)
• The correct exponent for the Gotsman-Linial conjecture
• Anticoncentration for subgraph statistics
• Resolution of the quadratic Littlewood-Offord problem

This page was built for publication: The Gotsman-Linial Conjecture is False

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607926)