2026-07-22T00:14:54Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17538 2024-03-06T10:59:51Z ddc:004 open_access

Black-Box Constructive Proofs Are Unavoidable Chen, Lijie Williams, Ryan Yang, Tianqi Circuit lower bounds natural proofs probabilistic checkable proofs 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Lijie Chen and Ryan Williams and Tianqi Yang 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.35 urn:nbn:de:0030-drops-175380 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.35 eng https://creativecommons.org/licenses/by/4.0/legalcode