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.35
URN: urn:nbn:de:0030-drops-175380
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2023/17538/
Chen, Lijie ;
Williams, Ryan ;
Yang, Tianqi
Black-Box Constructive Proofs Are Unavoidable
Abstract
Following Razborov and Rudich, a "natural property" for proving a circuit lower bound satisfies three axioms: constructivity, largeness, and usefulness. In 2013, Williams proved that for any reasonable circuit class C, NEXP ⊂ C is equivalent to the existence of a constructive property useful against C. Here, a property is constructive if it can be decided in poly(N) time, where N = 2ⁿ is the length of the truth-table of the given n-input function.
Recently, Fan, Li, and Yang initiated the study of black-box natural properties, which require a much stronger notion of constructivity, called black-box constructivity: the property should be decidable in randomized polylog(N) time, given oracle access to the n-input function. They showed that most proofs based on random restrictions yield black-box natural properties, and demonstrated limitations on what black-box natural properties can prove.
In this paper, perhaps surprisingly, we prove that the equivalence of Williams holds even with this stronger notion of black-box constructivity: for any reasonable circuit class C, NEXP ⊂ C is equivalent to the existence of a black-box constructive property useful against C. The main technical ingredient in proving this equivalence is a smooth, strong, and locally-decodable probabilistically checkable proof (PCP), which we construct based on a recent work by Paradise. As a by-product, we show that average-case witness lower bounds for PCP verifiers follow from NEXP lower bounds.
We also show that randomness is essential in the definition of black-box constructivity: we unconditionally prove that there is no deterministic polylog(N)-time constructive property that is useful against even polynomial-size AC⁰ circuits.
BibTeX - Entry
@InProceedings{chen_et_al:LIPIcs.ITCS.2023.35,
author = {Chen, Lijie and Williams, Ryan and Yang, Tianqi},
title = {{Black-Box Constructive Proofs Are Unavoidable}},
booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
pages = {35:1--35:24},
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/17538},
URN = {urn:nbn:de:0030-drops-175380},
doi = {10.4230/LIPIcs.ITCS.2023.35},
annote = {Keywords: Circuit lower bounds, natural proofs, probabilistic checkable proofs}
}
|
Keywords: |
|
Circuit lower bounds, natural proofs, probabilistic checkable proofs |
|
Collection: |
|
14th Innovations in Theoretical Computer Science Conference (ITCS 2023) |
|
Issue Date: |
|
2023 |
|
Date of publication: |
|
01.02.2023 |
