2026-07-25T03:03:36Z https://drops.dagstuhl.de/oai
oai:drops-oai.dagstuhl.de:17521 2024-03-06T10:59:48Z ddc:004 open_access
Certification with an NP Oracle Blanc, Guy Koch, Caleb Lange, Jane Strassle, Carmen Tan, Li-Yang Certificate complexity Boolean functions polynomial hierarchy hardness of approximation In the certification problem, the algorithm is given a function f with certificate complexity k and an input x^⋆, and the goal is to find a certificate of size ≀ poly(k) for f’s value at x^⋆. This problem is in NP^NP, and assuming 𝖯 β‰  NP, is not in 𝖯. Prior works, dating back to Valiant in 1984, have therefore sought to design efficient algorithms by imposing assumptions on f such as monotonicity. Our first result is a BPP^NP algorithm for the general problem. The key ingredient is a new notion of the balanced influence of variables, a natural variant of influence that corrects for the bias of the function. Balanced influences can be accurately estimated via uniform generation, and classic BPP^NP algorithms are known for the latter task. We then consider certification with stricter instance-wise guarantees: for each x^⋆, find a certificate whose size scales with that of the smallest certificate for x^⋆. In sharp contrast with our first result, we show that this problem is NP^NP-hard even to approximate. We obtain an optimal inapproximability ratio, adding to a small handful of problems in the higher levels of the polynomial hierarchy for which optimal inapproximability is known. Our proof involves the novel use of bit-fixing dispersers for gap amplification. Schloss Dagstuhl – Leibniz-Zentrum fΓΌr Informatik Guy Blanc and Caleb Koch and Jane Lange and Carmen Strassle and Li-Yang Tan 2023 Is Part Of LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ITCS.2023.18 urn:nbn:de:0030-drops-175217 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.18 eng https://creativecommons.org/licenses/by/4.0/legalcode