ACM Symposium on Theory of Computing (STOC)

The query complexity of certification

Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan

Published Jun 9, 2022• 2 citations

Abstract

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⋆.

DOI: 10.1145/3519935.3519993

Related papers

An Optimal Algorithm for Certifying Monotone Functions

Meghal Gupta, Naren Sarayu Manoj

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].

arXiv:2204.01224Society for Industrial and Applied Mathematics eBooksJan 1, 20230 citations

Randomized query complexity can beat certificate complexity

Shalev Ben-David, Robin Kothari

A long-standing open question in query complexity asks whether there is a total Boolean function f with R(f) << C(f), where R(f) and C(f) denote its bounded-error randomized query complexity and certificate complexity, respectively. We construct a function with R(f) = O~(sqrt{C(f)}), which is optimal up to log factors. The same function also has $Q(f) = O~(C(f)^{1/4}), where Q(f) is the bounded-error quantum query complexity of f, which is also nearly optimal.

cs.CCCross-listedarXiv:2609.15063Sep 15, 20260 citations

The Query Complexity of Certification

Guy Blanc, Koch, Caleb, Jane Lange +1 more

arXiv:2201.07736Jan 19, 20220 citations

Certification complexity of Boolean functions

Chandrima Kayal, Sophie Laplante, Émile Larroque +2 more

arXiv:2609.26757Sep 22, 20260 citations

The quantum query complexity of certification

Andris Ambainis, Andrew M. Childs, François Le Gall +1 more

Quantum Information and ComputationMar 1, 20109 citations

Between the deterministic and non-deterministic query complexity

Dániel Gerbner

arXiv:1907.09531Jul 22, 20190 citations

ACM Symposium on Theory of Computing (STOC)

The query complexity of certification

Guy Blanc, Caleb Koch, Jane Lange, Li-Yang Tan

Published Jun 9, 2022• 2 citations

Publisher

Abstract

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⋆.

DOI: 10.1145/3519935.3519993

Related papers

An Optimal Algorithm for Certifying Monotone Functions

Meghal Gupta, Naren Sarayu Manoj

arXiv:2204.01224Society for Industrial and Applied Mathematics eBooksJan 1, 20230 citations

Randomized query complexity can beat certificate complexity

Shalev Ben-David, Robin Kothari

cs.CCCross-listedarXiv:2609.15063Sep 15, 20260 citations

The Query Complexity of Certification

Guy Blanc, Koch, Caleb, Jane Lange +1 more

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 $Ω(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.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 $Ω(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.

arXiv:2201.07736Jan 19, 20220 citations

Certification complexity of Boolean functions

Chandrima Kayal, Sophie Laplante, Émile Larroque +2 more

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 $(Q_0)$ and exact query complexity $(Q_E)$ , 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 $Q_E$ and $Q_0$ , the quantum analogues of $D$ and $R_0$ , 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 $Q_0$ , but rational degree and $Q$ are asymptotically smaller.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 $(Q_0)$ and exact query complexity $(Q_E)$, 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 $Q_E$ and $Q_0$, the quantum analogues of $D$ and $R_0$, 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 $Q_0$, but rational degree and $Q$ are asymptotically smaller.

arXiv:2609.26757Sep 22, 20260 citations

The quantum query complexity of certification

Andris Ambainis, Andrew M. Childs, François Le Gall +1 more

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 $\tilde\Theta(d^{(k+1)/2})$ for 0-certificates, and $\tilde\Theta(d^{k/2})$ for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is $\tilde O(d^{(k+1)/2})$ . Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.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 $\tilde\Theta(d^{(k+1)/2})$ for 0-certificates, and $\tilde\Theta(d^{k/2})$ for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is $\tilde O(d^{(k+1)/2})$. Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

Quantum Information and ComputationMar 1, 20109 citations

Between the deterministic and non-deterministic query complexity

Dániel Gerbner

We consider problems that can be solved by asking certain queries. The deterministic query complexity $D(P,n)$ of a problem $P$ is the smallest number of queries needed to ask in order to find the solution with an input of size $n$ (in the worst case), while the non-deterministic query complexity $D_0(P,n)$ is the smallest number of queries needed to ask, in case we know the solution, to prove that it is indeed the solution (in the worst case). Equivalently, $D(P,n)$ is the largest number of queries needed to find the solution in case an Adversary is answering the queries, while $D_0(P)$ is the largest number of queries needed to find the solution in case an Adversary chooses the input. We define a series of quantities between these two values, $D_k(P,n)$ is the largest number of queries needed to find the solution in case an Adversary chooses the input, and answers the queries, but he can change the input at most $k$ times. We give bounds on $D_k(P,n)$ for various problems $P$ .We consider problems that can be solved by asking certain queries. The deterministic query complexity $D(P,n)$ of a problem $P$ is the smallest number of queries needed to ask in order to find the solution with an input of size $n$ (in the worst case), while the non-deterministic query complexity $D_0(P,n)$ is the smallest number of queries needed to ask, in case we know the solution, to prove that it is indeed the solution (in the worst case). Equivalently, $D(P,n)$ is the largest number of queries needed to find the solution in case an Adversary is answering the queries, while $D_0(P)$ is the largest number of queries needed to find the solution in case an Adversary chooses the input. We define a series of quantities between these two values, $D_k(P,n)$ is the largest number of queries needed to find the solution in case an Adversary chooses the input, and answers the queries, but he can change the input at most $k$ times. We give bounds on $D_k(P,n)$ for various problems $P$.

arXiv:1907.09531Jul 22, 20190 citations

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

Ω(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.

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

(Q_0)

and exact query complexity

(Q_E)

, 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

Q_E

and

Q_0

, the quantum analogues of

D

and

R_0

, 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

Q_0

, 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

\tilde\Theta(d^{(k+1)/2})

for 0-certificates, and

\tilde\Theta(d^{k/2})

for 1-certificates. In particular, this shows that the zero-error quantum query complexity of evaluating such formulas is

\tilde O(d^{(k+1)/2})

. Our lower bound relies on the fact that the quantum adversary method obeys a direct sum theorem.

We consider problems that can be solved by asking certain queries. The deterministic query complexity

D(P,n)

of a problem

P

is the smallest number of queries needed to ask in order to find the solution with an input of size

n

(in the worst case), while the non-deterministic query complexity

D_0(P,n)

is the smallest number of queries needed to ask, in case we know the solution, to prove that it is indeed the solution (in the worst case). Equivalently,

D(P,n)

is the largest number of queries needed to find the solution in case an Adversary is answering the queries, while

D_0(P)

is the largest number of queries needed to find the solution in case an Adversary chooses the input. We define a series of quantities between these two values,

D_k(P,n)

is the largest number of queries needed to find the solution in case an Adversary chooses the input, and answers the queries, but he can change the input at most

k

times. We give bounds on

D_k(P,n)

for various problems

P