Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz.

Jonas Conneryd, Susanna F. de Rezende, Jakob Nordstrm, Shuo Pang, Kilian Risse

Browse the full FOCS paper archive.