Given query access to a monotone function f: {0,1}n → {0,1} with certificate complexity C(f) and an input x*, we design an algorithm that outputs a size-C (f) subset of x* certifying the value of f(x*). Our algorithm makes O (C(f) · log n) queries to f, which matches the information-theoretic lower bound for this problem and resolves the main open question posed in the STOC 2022 paper of Blanc, Koch, Lange, and Tan [BKLT22].
Given query access to a monotone function f: {0,1}n → {0,1} with certificate complexity C(f) and an input x*, we design an algorithm that outputs a size-C (f) subset of x* certifying the value of f(x*). Our algorithm makes O (C(f) · log n) queries to f, which matches the information-theoretic lower bound for this problem and resolves the main open question posed in the STOC 2022 paper of Blanc, Koch, Lange, and Tan [BKLT22].
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.
In this work, we develop new insights into the fundamental problem of convexity testing of real-valued functions over the domain [n]. Specifically, we present a nonadaptive algorithm that, given inputs ε ∊ (0,1), s ∊ ℕ, and oracle access to a function, ε-tests convexity in O(log(s)/ε), where s is an upper bound on the number of distinct discrete derivatives of the function. We also show that this bound is tight. Since s ≤ n, our query complexity bound is at least as good as that of the optimal convexity tester (Ben Eliezer; ITCS 2019) with complexity ; our bound is strictly better when s = o(n). The main contribution of our work is to appropriately parameterize the complexity of convexity testing to circumvent the worst-case lower bound (Belovs et al.; SODA 2020) of expressed in terms of the input size and obtain a more efficient algorithm.
We consider the problem of quantum channel certification to unitary, where one is given access to an unknown d-dimensional channel E, and wants to test whether E is equal to a target unitary channel or is ε-far from it in the diamond norm. We present optimal quantum algorithms for this problem, settling the query complexities in three access models with increasing power. Specifically, we show that:
(i) Θ(d/ε2) queries suffice for incoherent access model, matching the lower bound due to Fawzi, Flammarion, Garivier, and Oufkir (COLT 2023).
(ii) Θ(d/ε) queries suffice for coherent access model, matching the lower bound due to Regev and Schiff (ICALP 2008).
(iii) Θ(d/ε) queries suffice for source-code access model, matching the lower bound due to Jeon and Oh (npj Quantum Inf. 2026).
This demonstrates a strict hierarchy of complexities for quantum channel certification to unitary across various access models.
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.