Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erdős-Rényi random graphs, are 3-colourable. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on proof size
| Original language | English |
|---|---|
| Title of host publication | Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023 |
| Number of pages | 11 |
| Publisher | IEEE Computer Society Press |
| Publication date | 2023 |
| Article number | 45 |
| ISBN (Electronic) | 979-8-3503-1894-4 |
| DOIs | |
| Publication status | Published - 2023 |
| Event | 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, United States Duration: 6 Nov 2023 → 9 Nov 2023 |
Conference
| Conference | 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 |
|---|---|
| Land | United States |
| By | Santa Cruz |
| Periode | 06/11/2023 → 09/11/2023 |
| Sponsor | IEEE, IEEE Computer Society, IEEE Computer Society Technical Committee on Mathematical Foundations of Computing, NSF |
| Series | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
|---|---|
| ISSN | 0272-5428 |
Bibliographical note
Publisher Copyright:
© 2023 IEEE.
- average-case complexity, polynomial calculus, Proof Complexity
Research areas
ID: 390450333