Publication

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

Kilian Risse
2023
Conference Papers

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.

Official source

Graph Chat

Chat with Graph Search

Ask any question about EPFL courses, lectures, exercises, research, news, etc. or try the example questions below.

DISCLAIMER: The Graph Chatbot is not programmed to provide explicit or categorical answers to your questions. Rather, it transforms your questions into API requests that are distributed across the various IT services officially administered by EPFL. Its purpose is solely to collect and recommend relevant references to content that you can explore to help you answer your questions.

Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz

Chat with Graph Search

Self-indexing Algorithms for Graph Representations of Genomic References

Parallelizing Maximal Clique Enumeration on Modern Manycore Processors