Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

Jonas Conneryd, Susanna F. de Rezende, Jakob Nordström +2

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…