The query complexity of certification
Li-Yang Tan (Stanford University)
E18-304
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…