Standard
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. / Conneryd, Jonas; de Rezende, Susanna F.; Nordström, Jakob; Pang, Shuo; Risse, Kilian.
Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society Press, 2023. 45 (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
Conneryd, J, de Rezende, SF
, Nordström, J, Pang, S & Risse, K 2023,
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. in
Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023., 45, IEEE Computer Society Press, Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS, 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, United States,
06/11/2023.
https://doi.org/10.1109/FOCS57990.2023.00007APA
Conneryd, J., de Rezende, S. F.
, Nordström, J., Pang, S., & Risse, K. (2023).
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. In
Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023 [45] IEEE Computer Society Press. Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
https://doi.org/10.1109/FOCS57990.2023.00007Vancouver
Conneryd J, de Rezende SF
, Nordström J, Pang S, Risse K.
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. In Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society Press. 2023. 45. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
https://doi.org/10.1109/FOCS57990.2023.00007Author
Conneryd, Jonas ; de Rezende, Susanna F. ; Nordström, Jakob ; Pang, Shuo ; Risse, Kilian. / Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz. Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. IEEE Computer Society Press, 2023. (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS).
Bibtex
@inproceedings{b5cdac46efea4c0faf193c0f4a2522fd,
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. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on proof size ",
keywords = "average-case complexity, polynomial calculus, Proof Complexity",
author = "Jonas Conneryd and {de Rezende}, {Susanna F.} and Jakob Nordstr{\"o}m and Shuo Pang and Kilian Risse",
note = "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",
booktitle = "Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023",
publisher = "IEEE Computer Society Press",
}
RIS
TY - GEN
T1 - Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
AU - Conneryd, Jonas
AU - de Rezende, Susanna F.
AU - Nordström, Jakob
AU - Pang, Shuo
AU - Risse, Kilian
N1 - 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. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on proof size
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. Using the known relation between size and degree for polynomial calculus proofs, this implies strongly exponential lower bounds on proof size
KW - average-case complexity
KW - polynomial calculus
KW - Proof Complexity
U2 - 10.1109/FOCS57990.2023.00007
DO - 10.1109/FOCS57990.2023.00007
M3 - Article in proceedings
AN - SCOPUS:85182394027
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
BT - Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
PB - IEEE Computer Society Press
T2 - 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
Y2 - 6 November 2023 through 9 November 2023
ER -
