The query complexity of certification

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

For monotone functions, a classic local search algorithm of Angluin accomplishes this task with n queries, which we show is optimal for local search algorithms. 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 Ω(k log n). The design and analysis of our algorithm are based on a new connection to threshold phenomena in monotone functions.

We further prove exponential-in-k lower bounds when f is non-monotone, and when f is monotone but the algorithm is only given random examples of f . These lower bounds show that assumptions on the structure of f and query access to it are both necessary for the polynomial dependence on k that we achieve.