Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

Jonas Conneryd; Susanna F. De Rezende; Jakob Nordstrom; Shuo Pang; Kilian Risse

doi:10.1109/FOCS57990.2023.00007

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

Jonas Conneryd, Susanna F. De Rezende, Jakob Nordstrom, Shuo Pang, Kilian Risse

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding › Peer review

Sammanfattning

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.

Originalspråk	engelska
Titel på värdpublikation	Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
Förlag	IEEE Computer Society
Sidor	1-11
Antal sidor	11
ISBN (elektroniskt)	9798350318944
DOI	https://doi.org/10.1109/FOCS57990.2023.00007
Status	Published - 2023
Evenemang	64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 - Santa Cruz, USA Varaktighet: 2023 nov. 6 → 2023 nov. 9

Publikationsserier

Namn	Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
ISSN (tryckt)	0272-5428

Konferens

Konferens	64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Land/Territorium	USA
Ort	Santa Cruz
Period	2023/11/06 → 2023/11/09

Bibliografisk information

Publisher Copyright:
© 2023 IEEE.

Ämnesklassifikation (UKÄ)

Datavetenskap (datalogi)

Tillgång till dokument

10.1109/FOCS57990.2023.00007

Citera det här

Conneryd, J., De Rezende, S. F., Nordstrom, J., Pang, S., & Risse, K. (2023). Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. I Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023 (s. 1-11). (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). IEEE Computer Society. https://doi.org/10.1109/FOCS57990.2023.00007

@inproceedings{b3ba0485363449d7bb21adccca03701d,

title = "Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz",

abstract = "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{\H o}s-R{\'e}nyi random graphs, are 3-colourable.",

keywords = "average-case complexity, polynomial calculus, Proof Complexity",

author = "Jonas Conneryd and {De Rezende}, {Susanna F.} and Jakob Nordstrom and Shuo Pang and Kilian Risse",

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{\"o}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{\"o}m together with Shuo Pang were supported by the Independent Research Fund Denmark grant 9040-00389B. Publisher Copyright: {\textcopyright} 2023 IEEE.; 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 ; Conference date: 06-11-2023 Through 09-11-2023",

year = "2023",

doi = "10.1109/FOCS57990.2023.00007",

language = "English",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "1--11",

booktitle = "Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023",

address = "United States",

}

Conneryd, J , De Rezende, SF , Nordstrom, J, Pang, S & Risse, K 2023, Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. i Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, IEEE Computer Society, s. 1-11, 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, USA, 2023/11/06. https://doi.org/10.1109/FOCS57990.2023.00007

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. / Conneryd, Jonas ; De Rezende, Susanna F.; Nordstrom, Jakob et al.
Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society, 2023. s. 1-11 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).

Forskningsoutput: Kapitel i bok/rapport/Conference proceeding › Konferenspaper i proceeding › Peer review

TY - GEN

T1 - Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

AU - Conneryd, Jonas

AU - De Rezende, Susanna F.

AU - Nordstrom, Jakob

AU - Pang, Shuo

AU - Risse, Kilian

N1 - 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.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

KW - average-case complexity

KW - polynomial calculus

KW - Proof Complexity

U2 - 10.1109/FOCS57990.2023.00007

DO - 10.1109/FOCS57990.2023.00007

M3 - Paper in conference proceeding

AN - SCOPUS:85182394027

T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS

SP - 1

EP - 11

BT - Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023

PB - IEEE Computer Society

T2 - 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023

Y2 - 6 November 2023 through 9 November 2023

ER -

Conneryd J , De Rezende SF , Nordstrom J, Pang S, Risse K. Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. I Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society. 2023. s. 1-11. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS). doi: 10.1109/FOCS57990.2023.00007

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

Sammanfattning

Publikationsserier

Konferens

Bibliografisk information

Ämnesklassifikation (UKÄ)

Tillgång till dokument

Fingeravtryck

Citera det här