We study the problem of {\sl 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⋆. 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(k8logn) queries, which comes close to matching the information-theoretic lower bound of
Ω(klogn). 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.
Certificate complexity
(C(f)) is a fundamental measure of complexity of Boolean functions f which counts the number of bits of an input that need to be known in order for the value of the function to be determined. A certificate can be viewed as a partial assignment, or a boolean subcube where the function is constant. Certificate complexity is well understood for deterministic query (or decision tree) complexity
(D) and other query models such as bounded-error randomized and quantum complexity
(R,Q), but not as well for quantum zero-error
(Q0) and exact query complexity
(QE), where there is no agreed-upon certificate 'object' (even for
Q). Instead, we study an operational notion of certification and apply it to various query-based models, with a focus on zero-error and exact quantum query complexity, but also on polynomial degree measures. We give new characterizations of
C,RC (randomized certificate complexity) and
QC (quantum certificate complexity), in terms of various measures such as classical and quantum sabotage complexity, unambiguous certificate complexity, and variants of polynomial degree. Certification complexity also gives rise to new lower bounds on
QE and
Q0, the quantum analogues of
D and
R0, complexity measures for which few lower bound techniques are known which are not already lower bounds for two-sided error quantum query complexity. We exhibit a total Boolean function for which our certification complexity measure gives a tight lower bound for
Q0, but rational degree and
Q are asymptotically smaller.
We study the quantum query complexity of finding a certificate for a d-regular, k-level balanced \nand formula. We show that the query complexity is
Θ~(d(k+1)/2) for 0-certificates, and
Θ~(dk/2) for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is
O~(d(k+1)/2). Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.
This chapter focuses on query complexity, which measures the minimum number of input bits that need to be read to solve a problem, in other words, the minimum depth of any correct decision tree (or branching program). Techniques for upper and lower bounds for deterministic and randomized query complexities are covered. The close relationships between query complexity and other measures known as certificate complexity and sensitivity are also covered. The chapter concludes with techniques for proving lower bounds on the size (as opposed to depth) of decision trees and branching programs.