Robust testing of low-dimensional functions

Anindya De, Elchanan Mossel, Joe Neeman

A natural problem in high-dimensional inference is to decide if a classifier $f:{\mathbb{R}}^n\to \{-1,1\}$ depends on a small number of linear directions of its input data.…