Degree-$d$ Chow Parameters Robustly Determine Degree-$d$ PTFs (and
  Algorithmic Applications)
  The degree-$d$ Chow parameters of a Boolean function $f: \{-1,1\}^n \to
\mathbb{R}$ are its degree at most $d$ Fourier coefficients. It is well-known
that degree-$d$ Chow parameters uniquely characterize degree-$d$ polynomial
threshold functions (PTFs) within the space of all bounded functions. In this
paper, we prove a robust version of this theorem: For $f$ any Boolean
degree-$d$ PTF and $g$ any bounded function, if the degree-$d$ Chow parameters
of $f$ are close to the degree-$d$ Chow parameters of $g$ in $\ell_2$-norm,
then $f$ is close to $g$ in $\ell_1$-distance. Notably, our bound relating the
two distances is completely independent of the dimension $n$. That is, we show
that Boolean degree-$d$ PTFs are {\em robustly identifiable} from their
degree-$d$ Chow parameters. Results of this form had been shown for the $d=1$
case~\cite{OS11:chow, DeDFS14}, but no non-trivial bound was previously known
for $d >1$.
  Our robust identifiability result gives the following algorithmic
applications: First, we show that Boolean degree-$d$ PTFs can be efficiently
approximately reconstructed from approximations to their degree-$d$ Chow
parameters. This immediately implies that degree-$d$ PTFs are efficiently
learnable in the uniform distribution $d$-RFA
model~\cite{BenDavidDichterman:98}. As a byproduct of our approach, we also
obtain the first low integer-weight approximations of degree-$d$ PTFs, for
$d>1$. As our second application, our robust identifiability result gives the
first efficient algorithm, with dimension-independent error guarantees, for
malicious learning of Boolean degree-$d$ PTFs under the uniform distribution.
