The query complexity of certification

We study the problem of certification: given queries to a function f : 0,1n → 0,1 with certificate complexity ≤ k and an input x⋆, output a size-k certificate for f’s value on x⋆.