Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Conneryd, Jonas; de Rezende, Susanna F.; Nordstrom, Jakob; Pang, Shuo; Risse, Kilian
2023

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

Details

Title Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
Author(s) Conneryd, Jonas ; de Rezende, Susanna F. ; Nordstrom, Jakob ; Pang, Shuo ; Risse, Kilian
Published in 2023 Ieee 64Th Annual Symposium On Foundations Of Computer Science, Focs
Pages 1-11
Conference 64th Annual IEEE Symposium on the Foundations of Computer Science (FOCS), NOV 06-09, 2023, Santa Cruz, CA
Date 2023-01-01
Publisher Ieee Computer Soc, Los Alamitos
ISSN 0272-5428
ISBN 979-8-3503-1894-4
Keywords
DOI https://doi.org/10.1109/FOCS57990.2023.00007
Other identifier(s) View record in Web of Science
Laboratories THL2
Record Appears in Scientific production and competences > I&C - School of Computer and Communication Sciences > IINFCOM > THL2 - Theory of Computation Laboratory 2
Peer-reviewed publications
Conference Papers
Work produced at EPFL
Published
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
Record creation date 2024-02-23