# The Query Complexity of Certification

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Jan 2022.

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

- [Logic-Based Explainability in Machine Learning](https://mlsanity.com/paper/2211.00541/) (2022)
- [A Query-Optimal Algorithm for Finding Counterfactuals](https://mlsanity.com/paper/2207.07072/) (2022)
- [Interpretable DNFs](https://mlsanity.com/paper/2505.21212/) (2025)

## Abstract (arXiv)

We study the problem of sl certification: given queries to a function f : 0,1n → 0,1 with certificate complexity ≤ k and an input x^star, output a size-k certificate for f's value on x^star. This abstractly models a central problem in explainable machine learning, where we think of f as a blackbox model that we seek to explain the predictions of. For monotone functions, a classic local search algorithm of Angluin accomplishes this task with n queries, which we show is optimal for local search algorithms. Our main result is a new algorithm for certifying monotone functions with O(k8 log n) queries, which comes close to matching the information-theoretic lower bound of Omega(k log n). The design and analysis of our algorithm are based on a new connection to threshold phenomena in monotone functions. We further prove exponential-in-k lower bounds when f is non-monotone, and when f is monotone but the algorithm is only given random examples of f. These lower bounds show that assumptions on the structure of f and query access to it are both necessary for the polynomial dependence on k that we achieve.