Robust testing of low-dimensional functions
  A natural problem in high-dimensional inference is to decide if a classifier
$f:\mathbb{R}^n \rightarrow \{-1,1\}$ depends on a small number of linear
directions of its input data. Call a function $g: \mathbb{R}^n \rightarrow
\{-1,1\}$, a linear $k$-junta if it is completely determined by some
$k$-dimensional subspace of the input space. A recent work of the authors
showed that linear $k$-juntas are testable. Thus there exists an algorithm to
distinguish between: 1. $f: \mathbb{R}^n \rightarrow \{-1,1\}$ which is a
linear $k$-junta with surface area $s$, 2. $f$ is $\epsilon$-far from any
linear $k$-junta with surface area $(1+\epsilon)s$, where the query complexity
of the algorithm is independent of the ambient dimension $n$.
  Following the surge of interest in noise-tolerant property testing, in this
paper we prove a noise-tolerant (or robust) version of this result. Namely, we
give an algorithm which given any $c>0$, $\epsilon>0$, distinguishes between 1.
$f: \mathbb{R}^n \rightarrow \{-1,1\}$ has correlation at least $c$ with some
linear $k$-junta with surface area $s$. 2. $f$ has correlation at most
$c-\epsilon$ with any linear $k$-junta with surface area at most $s$. The query
complexity of our tester is $k^{\mathsf{poly}(s/\epsilon)}$.
  Using our techniques, we also obtain a fully noise tolerant tester with the
same query complexity for any class $\mathcal{C}$ of linear $k$-juntas with
surface area bounded by $s$. As a consequence, we obtain a fully noise tolerant
tester with query complexity $k^{O(\mathsf{poly}(\log k/\epsilon))}$ for the
class of intersection of $k$-halfspaces (for constant $k$) over the Gaussian
space. Our query complexity is independent of the ambient dimension $n$.
Previously, no non-trivial noise tolerant testers were known even for a single
halfspace.
