The query complexity of certification

Abstract: 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.

–

Bio:  Li-Yang Tan is an assistant professor of computer science at Stanford.  He is broadly interested in theoretical computer science, with an emphasis on computational complexity.  A main theme in his work is the development of techniques to understand boolean function complexity, and the application of these techniques to a range of areas in theoretical computer science.  His work has been recognized with best paper awards at FOCS and CCC.