# Exact Learning of Juntas from Membership Queries

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jun 2017.

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

- [Towards a theory of model distillation](https://mlsanity.com/paper/2403.09053/) (2024)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [On Learning and Testing Decision Tree](https://mlsanity.com/paper/2108.04587/) (2021)
- [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)
- [Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure](https://mlsanity.com/paper/2609.37841/) (2026)

## Abstract (arXiv)

In this paper, we study adaptive and non-adaptive exact learning of Juntas from membership queries. We use new techniques to find new bounds, narrow some of the gaps between the lower bounds and upper bounds and find new deterministic and randomized algorithms with small query and time complexities. Some of the bounds are tight in the sense that finding better ones either gives a breakthrough result in some long-standing combinatorial open problem or needs a new technique that is beyond the existing ones.