# Junta correlation is testable

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Apr 2019.

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

- [On the Power of Interactive Proofs for Learning](https://mlsanity.com/paper/2404.08158/) (2024)
- [Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression](https://mlsanity.com/paper/2303.04859/) (2023)
- [Sample-Efficient Linear Regression with Self-Selection Bias](https://mlsanity.com/paper/2402.14229/) (2024)

## Abstract (arXiv)

The problem of tolerant junta testing is a natural and challenging problem which asks if the property of a function having some specified correlation with a k-Junta is testable. In this paper we give an affirmative answer to this question: We show that given distance parameters frac12 >cu>cℓ ≥ 0, there is a tester which given oracle access to f:-1,1n rightarrow -1,1, with query complexity  2k · mathsfpoly(k,1/|cu-cℓ|) and distinguishes between the following cases: 1. The distance of f from any k-junta is at least cu; 2. There is a k-junta g which has distance at most cℓ from f. This is the first non-trivial tester (i.e., query complexity is independent of n) which works for all 1/2 > cu > cℓ ≥ 0. The best previously known results by Blais et~ al., required cu ≥ 16 cℓ. In fact, with the same query complexity, we accomplish the stronger goal of identifying the most correlated k-junta, up to permutations of the coordinates. We can further improve the query complexity to mathsfpoly(k, 1/|cu-cℓ|) for the (weaker) task of distinguishing between the following cases: 1. The distance of f from any k'-junta is at least cu. 2. There is a k-junta g which is at a distance at most cℓ from f. Here k'=O(k2/|cu-cℓ|). Our main tools are Fourier analysis based algorithms that simulate oracle access to influential coordinates of functions.