Nearly optimal solutions for the Chow Parameters Problem and low-weight approximation of halfspaces

Anindya De, Ilias Diakonikolas, Vitaly Feldman +1

The \emph{Chow parameters} of a Boolean function $f:\{-1,1{\}}^n\to \{-1,1\}$ are its $n+1$ degree-0 and degree-1 Fourier coefficients. It has been known since 1961 (Chow, Tannenba…