Trade-offs between size and degree in polynomial calculus
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- Trade-Offs Between Size and Degree in
Final published version, 543 KB, PDF document
Building on [Clegg et al.’96], [Impagliazzo et al.’99] established that if an unsatisfiable k-CNF formula over n variables has a refutation of size S in the polynomial calculus resolution proof system, then this formula also has a refutation of degree k + O(n log S). The proof of this works by converting a small-size refutation into a small-degree one, but at the expense of increasing the proof size exponentially. This raises the question of whether it is possible to achieve both small size and small degree in the same refutation, or whether the exponential blow-up is inherent. Using and extending ideas from [Thapen’16], who studied the analogous question for the resolution proof system, we prove that a strong size-degree trade-off is necessary.
Original language | English |
---|---|
Title of host publication | 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 |
Editors | Thomas Vidick |
Publisher | Schloss Dagstuhl - Leibniz-Zentrum für Informatik |
Publication date | Jan 2020 |
Pages | 1-16 |
Article number | 72 |
ISBN (Electronic) | 9783959771344 |
DOIs | |
Publication status | Published - Jan 2020 |
Event | 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 - Seattle, United States Duration: 12 Jan 2020 → 14 Jan 2020 |
Conference
Conference | 11th Innovations in Theoretical Computer Science Conference, ITCS 2020 |
---|---|
Land | United States |
By | Seattle |
Periode | 12/01/2020 → 14/01/2020 |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 151 |
ISSN | 1868-8969 |
- Colored polynomial local search, PCR, Polynomial calculus, Polynomial calculus resolution, Proof complexity, Resolution, Size-degree trade-off
Research areas
ID: 251867228