The degree-$d$ Chow parameters of a Boolean function $f: \bn \to \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,
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.
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.

The proof of our robust identifiability result involves several new technical ingredients, including
the following structural result for degree-$d$ multivariate polynomials with very poor anti-concentration:
If $p$ is a degree-$d$ polynomial where $p(x)$ is {\em very} close to $0$ on a {\em large} number of points in $\bn$,
then there exists a degree-$d$ hypersurface that exactly passes though {\em almost all} of these points.
We leverage this structural result to show that if the degree-$d$ Chow distance between $f$ and $g$ is small,
then we can find many degree-$d$ polynomials that vanish on their disagreement region,
and in particular enough that forces the $\ell_1$-distance between $f$ and $g$ to also be small.
To implement this proof strategy, we require additional technical ideas.
In particular, in the $d=2$ case we show that for any large vector space of degree-$2$ polynomials
with a large number of common zeroes, there exists a linear function that vanishes on almost all of these zeroes.
The degree-$d$ degree generalization of this statement is significantly more complex, and can be viewed as an effective version
of Hilbert's Basis Theorem for our setting.