The query complexity of certification

DOI10.1145/3519935.3519993MaRDI QIDQ6083517zbMATH OpenOpenAlexFDO

Authors Guy Blanc, Caleb M. Koch, Jane Lange, Li-Yang Tan

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2201.07736, https://hdl.handle.net/1721.1/146447

zbMATH Keywords

Boolean function complexitycertificate complexitymonotone functionsquery algorithms

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: We study the problem of {sl certification}: given queries to a function $f:{0,1}^{n}o0,1$ with certificate complexity $lek$ and an input $x^{s}tar$, output a size-$k$ certificate for $f$'s value on $x^{s}tar$. 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}logn)$ queries, which comes close to matching the information-theoretic lower bound of $Omega(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.

Recommendations

• The quantum query complexity of certification
• Certified complexity (CerCo)
• scientific article; zbMATH DE number 2044532
• Query Learning and Certificates in Lattices
• Certification of complexity proofs using CeTA
• The complexity of higher-order queries
• On the complexity of database queries
• Quantum certificate complexity
• The complexity of evaluating relational queries
• From query complexity to computational complexity

Cited in

(1)

• Resource bound certification

This page was built for publication: The query complexity of certification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083517)