# Learning and Testing Junta Distributions with Subcube Conditioning

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

## Key facts

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

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

- [Learning Hidden Markov Models Using Conditional Samples](https://mlsanity.com/paper/2302.14753/) (2023)
- [Model Stealing for Any Low-Rank Language Model](https://mlsanity.com/paper/2411.07536/) (2024)
- [Lifting uniform learners via distributional decomposition](https://mlsanity.com/paper/2303.16208/) (2023)
- [Complexity of High-Dimensional Identity Testing with Coordinate Conditional Sampling](https://mlsanity.com/paper/2207.09102/) (2022)
- [Gaussian Mean Testing Made Simple](https://mlsanity.com/paper/2210.13706/) (2022)
- [A Distributional-Lifting Theorem for PAC Learning](https://mlsanity.com/paper/2506.16651/) (2025)
- [Uniformity Testing over Hypergrids with Subcube Conditioning](https://mlsanity.com/paper/2302.09013/) (2023)
- [Optimal Algorithms for Augmented Testing of Discrete Distributions](https://mlsanity.com/paper/2412.00974/) (2024)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Sampling and Identity-Testing Without Approximate Tensorization of Entropy](https://mlsanity.com/paper/2506.23456/) (2025)
- [Agnostic PAC Learning of k-juntas Using L2-Polynomial Regression](https://mlsanity.com/paper/2303.04859/) (2023)
- [New Statistical and Computational Results for Learning Junta Distributions](https://mlsanity.com/paper/2505.05819/) (2025)
- [Testing Distributions Against Bounded Distinguishers](https://mlsanity.com/paper/2607.15645/) (2026)

## Abstract (arXiv)

We study the problems of learning and testing junta distributions on -1,1n with respect to the uniform distribution, where a distribution p is a k-junta if its probability mass function p(x) depends on a subset of at most k variables. The main contribution is an algorithm for finding relevant coordinates in a k-junta distribution with subcube conditioning [BC18, CCKLW20]. We give two applications: 1. An algorithm for learning k-junta distributions with tildeO(k/ε2) log n + O(2k/ε2) subcube conditioning queries, and 2. An algorithm for testing k-junta distributions with tildeO((k + √n)/ε2) subcube conditioning queries. All our algorithms are optimal up to poly-logarithmic factors. Our results show that subcube conditioning, as a natural model for accessing high-dimensional distributions, enables significant savings in learning and testing junta distributions compared to the standard sampling model. This addresses an open question posed by Aliakbarpour, Blais, and Rubinfeld [ABR17].