[Colloquium] CS Theory Seminar: Tuesday, May 6, 2025 - Kent 102

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS




Jakob Nordström
University of Copenhagen

 [cid:image001.jpg at 01DBB04F.14E357B0]

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.

Bio:  Jakob Nordström obtained his PhD in Computer Science at KTH Royal Institute of Technology in 2008.  During 2008 – 2010, he was a postdoctoral researcher at MIT.  In 2019, he moved to the University of Copenhagen, where he is now a full professor, and since 2020, he has also had a part-time affiliation with Lund University.





  Host: Alexander Razborov








-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250502/079e678c/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: image001.jpg
Type: image/jpeg
Size: 1536436 bytes
Desc: image001.jpg
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20250502/079e678c/attachment-0001.jpg>