The query complexity of certification

We study the problem of certification: given queries to an n-variable boolean function f with certificate complexity k and an input x, output a size-k certificate for f’s value on x. This abstractly models a problem of interest in explainable machine learning, where we think of f as a blackbox model that we seek to explain the predictions of.

For monotone functions, classic algorithms of Valiant and Angluin accomplish this task with n queries to f. Our main result is a new algorithm for certifying monotone functions with O(k^8 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.

Joint work with Guy Blanc, Caleb Koch, and Jane Lange. Available at https://arxiv.org/abs/2201.07736.