[Proof Complexity] MIAO seminar Thu Dec 5 at 14:00 CET with Shuo Pang: Colouring is hard on average for polynomial calculus and Nullstellensatz

[Jakob Nordström]

Dear all,

On Thursday December 5 at 14:00 CET we will have the opportunity to 
listen to the MIAO seminar "Colouring is hard on average for polynomial 
calculus and Nullstellensatz" given by our very own Shuo Pang from the 
University of Copenhagen and Lund University. You find the abstract at 
the bottom of this message.

We will run this as a hybrid seminar at the University of Copenhagen. 
Local participants are warmly welcome to room 20-1-123, BIO-Aqua, 
Building 20 at Universitetsparken 4, while other participants are 
equally warmly welcome to join virtually at 
https://lu-se.zoom.us/j/61925271827 . Please feel free to share this 
information with colleagues who you think might be interested. We are 
also hoping to record the seminar and post on the MIAO Research YouTube 
channel https://youtube.com/@MIAOresearch for people who would like to 
hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular 
talk, and then after a break a ca-1-hour in-depth technical presentation 
with (hopefully) a lot of interaction. The intention is that the first 
part of the seminar will give all listeners a self-contained overview of 
some exciting research results, and after the break people who have the 
time and interest will get an opportunity to really get into the 
technical details. (However, for those who feel that the first part was 
enough, it is perfectly fine to just discretely drop out during the 
break. No questions asked; no excuses needed.)

More information about the MIAO seminar series can be found at 
https://jakobnordstrom.se/miao-seminars/ . If you do not wish to receive 
these announcements, or receive several copies of them, please send a 
message to jn at di.ku.dk.

Best regards,
Jakob Nordström

**********

/Thursday Dec 5 at 14:00 in room 20-1-123, BIO-Aqua, Building 20, 
Universitetsparken 4, University of Copenhagen, and on Zoom
*Colouring is hard on average for polynomial calculus and Nullstellensatz
*(Shuo Pang, University of Copenhagen and Lund University)
/
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 Conneryd, Susanna F. de Rezende, Jakob 
Nordström, and Kilian Risse that appeared at FOCS 2023.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +45 28 78 38 11 / +46 70 742 21 98
https://jakobnordstrom.se