Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Documents
- OA-LIPIcs-CCC-2019-18
Final published version, 511 KB, PDF document
We establish an exactly tight relation between reversible pebblings of graphs and Nullstellensatz refutations of pebbling formulas, showing that a graph G can be reversibly pebbled in time t and space s if and only if there is a Nullstellensatz refutation of the pebbling formula over G in size t+1 and degree s (independently of the field in which the Nullstellensatz refutation is made). We use this correspondence to prove a number of strong size-degree trade-offs for Nullstellensatz, which to the best of our knowledge are the first such results for this proof system.
Original language | English |
---|---|
Title of host publication | 34th Computational Complexity Conference (CCC 2019), Proceedings |
Volume | 137 |
Publisher | Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik |
Publication date | 2019 |
Pages | 1-16 |
Article number | 18 |
ISBN (Electronic) | 978-3-95977-116-0 |
DOIs | |
Publication status | Published - 2019 |
Event | 34th Computational Complexity Conference, CCC 2019 - New Brunswick, United States Duration: 18 Jul 2019 → 20 Jul 2019 |
Conference
Conference | 34th Computational Complexity Conference, CCC 2019 |
---|---|
Land | United States |
By | New Brunswick |
Periode | 18/07/2019 → 20/07/2019 |
Sponsor | Microsoft Research |
Series | Leibniz International Proceedings in Informatics, LIPIcs |
---|---|
Volume | 137 |
ISSN | 1868-8969 |
- proof complexity, Nullstellensatz, pebble games, trade-offs, size, degree
Research areas
Number of downloads are based on statistics from Google Scholar and www.ku.dk
No data available
ID: 242305168