Lower Bounds: From Circuits to QBF Proof Systems
- Submitting institution
-
The University of Leeds
- Unit of assessment
- 11 - Computer Science and Informatics
- Output identifier
- UOA11-2638
- Type
- E - Conference contribution
- DOI
-
10.1145/2840728.2840740
- Title of conference / published proceedings
- Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science
- First page
- 249
- Volume
- -
- Issue
- -
- ISSN
- -
- Open access status
- -
- Month of publication
- January
- Year of publication
- 2016
- URL
-
-
- Supplementary information
-
-
- Request cross-referral to
- -
- Output has been delayed by COVID-19
- No
- COVID-19 affected output statement
- -
- Forensic science
- No
- Criminology
- No
- Interdisciplinary
- No
- Number of additional authors
-
2
- Research group(s)
-
A - AC (Algorithms and Complexity)
- Citation count
- 21
- Proposed double-weighted
- No
- Reserve for an output with double weighting
- No
- Additional information
- A long-standing belief in the proof complexity community postulates close connections between lower bounds for Boolean circuits and for proof size in propositional proof systems. A formal connection had not so far been established but we provide such a formal relation between circuit lower bounds and lower bounds for Frege systems for quantified Boolean formulas. This paper formed part of Chew’s PhD, and helped him obtain an EPSRC Prize Fellowship and subsequent postdoc at CMU. After Beyersdorff returned to his native Germany, an extended version appeared in JACM(https://dl.acm.org/doi/abs/10.1145/3381881). It also led to a John Templeton Foundation grant (#60842, $766k).
- Author contribution statement
- -
- Non-English
- No
- English abstract
- -
