Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Publikation: Bidrag til bog/antologi/rapport › Konferencebidrag i proceedings › Forskning › fagfællebedømt
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
| Originalsprog | Engelsk |
|---|---|
| Titel | Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023 |
| Antal sider | 11 |
| Forlag | IEEE Computer Society Press |
| Publikationsdato | 2023 |
| Artikelnummer | 45 |
| ISBN (Elektronisk) | 979-8-3503-1894-4 |
| DOI | |
| Status | Udgivet - 2023 |
| Begivenhed | 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, USA Varighed: 6 nov. 2023 → 9 nov. 2023 |
Konference
| Konference | 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 |
|---|---|
| Land | USA |
| 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 |
| Navn | Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS |
|---|---|
| ISSN | 0272-5428 |
Bibliografisk note
Funding Information:
Susanna F. de Rezende received funding from ELLIIT, from the Knut and Alice Wallenberg grant KAW 2021.0307, and from the Swedish Research Council grant 2021-05104. Kilian Risse was supported by the Swiss National Science Foundation project 200021-184656 “Randomness in Problem Instances and Randomized Algorithms”. Jonas Conneryd and Jakob Nordström were funded by the Swedish Research Council grant 2016-00782, and in addition Jonas Conneryd was also partially supported by the Wallenberg AI, Autonomous Systems and Software Program (WASP) funded by the Knut and Alice Wallenberg Foundation, whereas Jakob Nordström together with Shuo Pang were supported by the Independent Research Fund Denmark grant 9040-00389B.
Publisher Copyright:
© 2023 IEEE.
ID: 390450333