Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
2023
Résumé
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 Erdos-Renyi 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.
Détails
Titre
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Auteur(s)
Conneryd, Jonas ; de Rezende, Susanna F. ; Nordstrom, Jakob ; Pang, Shuo ; Risse, Kilian
Publié dans
2023 Ieee 64Th Annual Symposium On Foundations Of Computer Science, Focs
Pages
1-11
Présenté à
64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS), NOV 06-09, 2023, Santa Cruz, CA
Date
2023-01-01
Editeur
Ieee Computer Soc, Los Alamitos
ISSN
0272-5428
ISBN
979-8-3503-1894-4
Mots-clés (libres)
Autres identifiant(s)
Afficher la publication dans Web of Science
Laboratoires
THL2
Le document apparaît dans
Production scientifique et compétences > I&C - Faculté Informatique & Communications > IINFCOM > THL2 - Laboratoire de théorie du calcul 2
Publications validées par des pairs
Papiers de conférence
Travail produit à l'EPFL
Publié
Publications validées par des pairs
Papiers de conférence
Travail produit à l'EPFL
Publié
Grant
ELLIIT
Knut and Alice Wallenberg grant: KAW 2021.0307
Swedish Research Council: 2021-05104
Swiss National Science Foundation: 200021-184656
Wallenberg AI, Autonomous Systems and Software Program (WASP) - Knut and Alice Wallenberg Foundation
Independent Research Fund Denmark: 9040-00389B
Knut and Alice Wallenberg grant: KAW 2021.0307
Swedish Research Council: 2021-05104
Swiss National Science Foundation: 200021-184656
Wallenberg AI, Autonomous Systems and Software Program (WASP) - Knut and Alice Wallenberg Foundation
Independent Research Fund Denmark: 9040-00389B
Date de création de la notice
2024-02-23