  We study the problem of {\sl certification}: given queries to a function $f :
\{0,1\}^n \to \{0,1\}$ with certificate complexity $\le k$ and an input
$x^\star$, output a size-$k$ certificate for $f$'s value on $x^\star$. This
abstractly models a central problem in explainable machine learning, where we
think of $f$ as a blackbox model that we seek to explain the predictions of.
  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 $\Omega(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.
