Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

Conneryd, Jonas LU orcid ; De Rezende, Susanna F. LU orcid ; Nordstrom, Jakob LU ; Pang, Shuo and Risse, Kilian LU (2023) 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023 In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS p.1-11
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ős-Rényi random graphs, are 3-colourable.

Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
keywords
average-case complexity, polynomial calculus, Proof Complexity
host publication
Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023
series title
Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
pages
11 pages
publisher
IEEE Computer Society
conference name
64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023
conference location
Santa Cruz, United States
conference dates
2023-11-06 - 2023-11-09
external identifiers
  • scopus:85182394027
ISSN
0272-5428
ISBN
9798350318944
DOI
10.1109/FOCS57990.2023.00007
language
English
LU publication?
yes
additional info
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
b3ba0485-3634-49d7-bb21-adccca03701d
date added to LUP
2024-01-28 15:06:08
date last changed
2024-02-02 15:33:28
@inproceedings{b3ba0485-3634-49d7-bb21-adccca03701d,
  abstract     = {{<p>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.</p>}},
  author       = {{Conneryd, Jonas and De Rezende, Susanna F. and Nordstrom, Jakob and Pang, Shuo and Risse, Kilian}},
  booktitle    = {{Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023}},
  isbn         = {{9798350318944}},
  issn         = {{0272-5428}},
  keywords     = {{average-case complexity; polynomial calculus; Proof Complexity}},
  language     = {{eng}},
  pages        = {{1--11}},
  publisher    = {{IEEE Computer Society}},
  series       = {{Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS}},
  title        = {{Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz}},
  url          = {{http://dx.doi.org/10.1109/FOCS57990.2023.00007}},
  doi          = {{10.1109/FOCS57990.2023.00007}},
  year         = {{2023}},
}