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.MFCS.2021.29
URN: urn:nbn:de:0030-drops-144698
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2021/14469/
Chapman, Brynmor K. ;
Williams, R. Ryan
Black-Box Hypotheses and Lower Bounds
Abstract
What sort of code is so difficult to analyze that every potential analyst can discern essentially no information from the code, other than its input-output behavior? In their seminal work on program obfuscation, Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan, and Yang (CRYPTO 2001) proposed the Black-Box Hypothesis, which roughly states that every property of Boolean functions which has an efficient "analyst" and is "code independent" can also be computed by an analyst that only has black-box access to the code. In their formulation of the Black-Box Hypothesis, the "analysts" are arbitrary randomized polynomial-time algorithms, and the "codes" are general (polynomial-size) circuits. If true, the Black-Box Hypothesis would immediately imply NP ̸ ⊂ BPP.
We consider generalized forms of the Black-Box Hypothesis, where the set of "codes" ? and the set of "analysts" ? may correspond to other efficient models of computation, from more restricted models such as AC⁰ to more general models such as nondeterministic circuits. We show how lower bounds of the form ? ̸ ⊂ ? often imply a corresponding Black-Box Hypothesis for those respective codes and analysts. We investigate the possibility of "complete" problems for the Black-Box Hypothesis: problems in ? such that they are not in ? if and only if their corresponding Black-Box Hypothesis is true. Along the way, we prove an equivalence: for nondeterministic circuit classes ?, the "?-circuit satisfiability problem" is not in ? if and only if the Black-Box Hypothesis is true for analysts in ?.
BibTeX - Entry
@InProceedings{chapman_et_al:LIPIcs.MFCS.2021.29,
author = {Chapman, Brynmor K. and Williams, R. Ryan},
title = {{Black-Box Hypotheses and Lower Bounds}},
booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)},
pages = {29:1--29:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-201-3},
ISSN = {1868-8969},
year = {2021},
volume = {202},
editor = {Bonchi, Filippo and Puglisi, Simon J.},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14469},
URN = {urn:nbn:de:0030-drops-144698},
doi = {10.4230/LIPIcs.MFCS.2021.29},
annote = {Keywords: Black-Box hypothesis, circuit complexity, lower bounds}
}
|
Keywords: |
|
Black-Box hypothesis, circuit complexity, lower bounds |
|
Collection: |
|
46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021) |
|
Issue Date: |
|
2021 |
|
Date of publication: |
|
18.08.2021 |
