The Query Complexity of Certification

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.