- This event has passed.
The query complexity of certification
April 8 @ 11:00 am - 12:00 pm
Li-Yang Tan, Stanford University
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.