Loading Events
  • This event has passed.
Stochastics and Statistics Seminar Series

The query complexity of certification

April 8, 2022 @ 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.

MIT Institute for Data, Systems, and Society
Massachusetts Institute of Technology
77 Massachusetts Avenue
Cambridge, MA 02139-4307