<html><head><meta http-equiv="content-type" content="text/html; charset=utf-8"></head><body dir="auto"><div dir="ltr" style="-webkit-text-size-adjust: auto;"><b style="font-family: Calibri, sans-serif; font-size: 10pt;"><span style="font-size: 14pt; font-family: Helvetica;">Jakob Nordström</span></b><div dir="ltr"></div></div><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 14pt; font-family: Helvetica;">University of Copenhagen</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"> <o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><img width="309" height="209" id="Picture_x0020_3" src="cid:716622FA-E7AA-4B50-8083-77D2F7B1B9EC" alt="image001.jpg" style="width: 3.2187in; height: 2.177in;"><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span> <o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt;"><span dir="ltr">Tuesday, </span></span></b><b><span style="font-size: 11pt;"><span dir="ltr"><span dir="ltr">May 6</span></span><span dir="ltr"><span dir="ltr">, 202</span></span><span dir="ltr"><span dir="ltr">5,</span></span><span dir="ltr"><span dir="ltr"> at 3:30pm</span></span></span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><span style="font-size: 11pt; background: yellow;">Location: Kent 102</span></b><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 11pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt;"> </span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><b><i><span style="font-size: 14pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);">Title:</span></i></b><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);"> </span><span style="font-size: 14pt; font-family: "Times New Roman", serif; color: rgb(33, 33, 33);">Colouring is Hard on Average for Polynomial Calculus and Nullstellensatz</span><o:p></o:p></p><p class="MsoNormal" style="-webkit-text-size-adjust: auto; margin: 0in; font-size: 10pt; font-family: Calibri, sans-serif;"><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);"><br></span><b><i><span style="font-size: 14pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);">Abstract:</span></i></b><span style="font-size: 12pt; font-family: Aptos, sans-serif; color: rgb(33, 33, 33);"> </span><span style="font-size: 14pt; font-family: "Times New Roman", serif; color: rgb(33, 33, 33);">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.<br><br>This is joint work with Jonas Connery, Susanna F. de Rezende, Shuo Pang, and Kilian Risse that appeared at FOCS 2023. </span></p><div dir="ltr"></div></body></html>