[Theory] UC Theory Seminar

[Alexander Razborov via Theory]

 Jakob Nordström
University of Copenhagen
 
 
  
Tuesday, May 6, 2025, at 3:30pm
Location: Kent 102
 
 
 
Title: Colouring is Hard on Average for Polynomial Calculus and Nullstellensatz

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 Erdős-Rényi 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. It also means that algorithms based on Hilbert’s Nullstellensatz or Gröbner bases must require exponential running time for almost all such graphs.

This is joint work with Jonas Connery, Susanna F. de Rezende, Shuo Pang, and Kilian Risse that appeared at FOCS 2023. 
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250429/a8544108/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 299944 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20250429/a8544108/attachment-0001.jpg>