Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
We show that algebraic proofs are hard to find: Given an unsatisfiable CNF formula F, it is NP-hard to find a refutation of F in the Nullstellensatz, Polynomial Calculus, or Sherali-Adams proof systems in time polynomial in the size of the shortest such refutation. Our work extends, and gives a simplified proof of, the recent breakthrough of Atserias and Müller (JACM 2020) that established an analogous result for Resolution.
| Original language | English |
|---|---|
| Title of host publication | STOC 2021 - Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing |
| Editors | Samir Khuller, Virginia Vassilevska Williams |
| Publisher | Association for Computing Machinery |
| Pages | 209-222 |
| Number of pages | 14 |
| ISBN (Electronic) | 9781450380539 |
| DOIs | |
| State | Published - 15 Jun 2021 |
| Event | 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 - Virtual, Online, Italy Duration: 21 Jun 2021 → 25 Jun 2021 |
| Name | Proceedings of the Annual ACM Symposium on Theory of Computing |
|---|---|
| ISSN (Print) | 0737-8017 |
| Conference | 53rd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2021 |
|---|---|
| Country/Territory | Italy |
| City | Virtual, Online |
| Period | 21/06/21 → 25/06/21 |
ID: 84277175