Conference item
From proof complexity to circuit complexity via interactive protocols
- Abstract:
-
Folklore in complexity theory suspects that circuit lower bounds against NC1 or P/poly, currently out of reach, are a necessary step towards proving strong proof complexity lower bounds for systems like Frege or Extended Frege. Establishing such a connection formally, however, is already daunting, as it would imply the breakthrough separation NEXP ⊈ P/poly, as recently observed by Pich and Santhanam [Pich and Santhanam, 2023].
We show such a connection conditionally for the Implicit Extended Frege proof system (iEF) introduced by Krajíček [Krajíček, 2004], capable of formalizing most of contemporary complexity theory. In particular, we show that if iEF proves efficiently the standard derandomization assumption that a concrete Boolean function is hard on average for subexponential-size circuits, then any superpolynomial lower bound on the length of iEF proofs implies #P ⊈ FP/poly (which would in turn imply, for example, PSPACE ⊈ P/poly). Our proof exploits the formalization inside iEF of the soundness of the sum-check protocol of Lund, Fortnow, Karloff, and Nisan [Lund et al., 1992]. This has consequences for the self-provability of circuit upper bounds in iEF. Interestingly, further improving our result seems to require progress in constructing interactive proof systems with more efficient provers.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 672.5KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.ICALP.2024.12
Authors
- Publisher:
- Schloss Dagstuhl – Leibniz-Zentrum für Informatik
- Host title:
- 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
- Volume:
- 297
- Pages:
- 12:1-12:20
- Article number:
- 12
- Series:
- Leibniz International Proceedings in Informatics (LIPIcs)
- Publication date:
- 2024-07-02
- Acceptance date:
- 2024-04-14
- Event title:
- 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2024)
- Event location:
- Tallinn, Estonia
- Event website:
- https://compose.ioc.ee/icalp2024/
- Event start date:
- 2024-07-08
- Event end date:
- 2024-07-12
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959773225
- Language:
-
English
- Keywords:
- Pubs id:
-
2007374
- Local pid:
-
pubs:2007374
- Deposit date:
-
2024-06-09
Terms of use
- Copyright holder:
- Arteche et al.
- Copyright date:
- 2024
- Rights statement:
- © Noel Arteche, Erfan Khaniki, Ján Pich, and Rahul Santhanam; licensed under Creative Commons License CC-BY 4.0.
- Notes:
-
This paper was presented at the 51st EATCS International Colloquium on Automata, Languages, and Programming (ICALP 2024), 8th-12th July 2024, Tallinn, Estonia.
This is the accepted manuscript version of the article. The published version is available online from Schloss Dagstuhl – Leibniz-Zentrum für Informatik at https://dx.doi.org/10.4230/LIPIcs.ICALP.2024.12
For the purpose of Open Access, the authors have applied a CC BY public copyright license to any Author Accepted Manuscript version arising from this submission.
- Licence:
- CC Attribution (CC BY)
If you are the owner of this record, you can report an update to it here: Report update to this record