# Robust testing of low-dimensional functions

arXiv: https://arxiv.org/abs/2004.11642 · HTML: https://mlsanity.com/paper/2004.11642/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Apr 2020.

## Built on by (most cited first, 4 of 4)

- [Survey on Algorithms for multi-index models](https://mlsanity.com/paper/2504.05426/) (2025)
- [Smoothed Analysis for Learning Concepts with Low Intrinsic Dimension](https://mlsanity.com/paper/2407.00966/) (2024)
- [Learning and Testing Convex Functions](https://mlsanity.com/paper/2511.11498/) (2025)
- [Sparsifying Suprema of Gaussian Processes](https://mlsanity.com/paper/2411.14664/) (2024)

## Abstract (arXiv)

A natural problem in high-dimensional inference is to decide if a classifier f:ℝn rightarrow -1,1 depends on a small number of linear directions of its input data. Call a function g: ℝ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: ℝn rightarrow -1,1 which is a linear k-junta with surface area s, 2. f is ε-far from any linear k-junta with surface area (1+ε)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, ε>0, distinguishes between 1. f: ℝ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-ε with any linear k-junta with surface area at most s. The query complexity of our tester is k^mathsfpoly(s/ε). Using our techniques, we also obtain a fully noise tolerant tester with the same query complexity for any class 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(mathsfpoly(log k/ε)) 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.