A Refutation of the Gotsman-Linial Conjecture

Prelegent(ci)

Brynmor Chapman

Afiliacja

Massachusetts Institute of Technology

Termin

6 lipca 2017 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

A degree-$d$ polynomial threshold function is a function that can be written as the sign of a degree-$d$ polynomial on the Boolean hypercube.  Bounds on the sensitivity of polynomial threshold functions to small changes in their inputs have many applications in circuit complexity and learning theory.  In 1991, Craig Gotsman and Nathan Linial conjectured that for all $n$ and $d$, the average sensitivity (sensitivity to a change in one random input bit) 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.

---