License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2023.18
URN: urn:nbn:de:0030-drops-175217
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17521/
Blanc, Guy ;
Koch, Caleb ;
Lange, Jane ;
Strassle, Carmen ;
Tan, Li-Yang
Certification with an NP Oracle
Abstract
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.
BibTeX - Entry
@InProceedings{blanc_et_al:LIPIcs.ITCS.2023.18,
author = {Blanc, Guy and Koch, Caleb and Lange, Jane and Strassle, Carmen and Tan, Li-Yang},
title = {{Certification with an NP Oracle}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {18:1--18:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-263-1},
ISSN = {1868-8969},
year = {2023},
volume = {251},
editor = {Tauman Kalai, Yael},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2023/17521},
URN = {urn:nbn:de:0030-drops-175217},
doi = {10.4230/LIPIcs.ITCS.2023.18},
annote = {Keywords: Certificate complexity, Boolean functions, polynomial hierarchy, hardness of approximation}
}
|
Keywords: |
|
Certificate complexity, Boolean functions, polynomial hierarchy, hardness of approximation |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
