# Exact Learning from an Honest Teacher That Answers Membership Queries

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

## Key facts

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

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

- [Efficient Multiple Constraint Acquisition](https://mlsanity.com/paper/2109.05920/) (2021)
- [Learning Low Degree Hypergraphs](https://mlsanity.com/paper/2202.09989/) (2022)
- [Positive Distribution Shift as a Framework for Understanding Tractable Learning](https://mlsanity.com/paper/2602.08907/) (2026)
- [Approximating the Number of Relevant Variables in a Parity Implies Proper Learning](https://mlsanity.com/paper/2407.11832/) (2024)
- [On Learning and Testing Decision Tree](https://mlsanity.com/paper/2108.04587/) (2021)
- [Optimal Quantum-Classical Separations for Exact Learning](https://mlsanity.com/paper/2609.38073/) (2026)

## Abstract (arXiv)

Given a teacher that holds a function f:X→ R from some class of functions C. The teacher can receive from the learner an element~d in the domain X (a query) and returns the value of the function in d, f(d)∈ R. The learner goal is to find f with a minimum number of queries, optimal time complexity, and optimal resources. In this survey, we present some of the results known from the literature, different techniques used, some new problems, and open problems.