[Proof Complexity] MIAO seminar Mon Oct 13 at 10:00 CE(S)T (note the time!) with Marc Vinyals: Lifting with colourful sunflowers

[Jakob Nordström]

Dear all,

On Monday October 13 at 10:00 CE(S)T (note the time!), we will have the pleasure of listening to a presentation by Marc Vinyals from the University of Auckland titled "Lifting with colourful sunflowers". You find the abstract at the bottom of this message.

This will be a video seminar 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.

More information about the MIAO seminar series can be found at https://jakobnordstrom.se/miao-seminars/ . In particular, note that tomorrow Monday October 6 at 14:00 we will have a seminar with Bruno Pasqualotto Cavalar on the latest news in circuit complexity. 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

**********

/Monday Oct 13 at 10:00 (note the time!) on Zoom
*Lifting with colourful sunflowers
*(Marc Vinyals, University of Auckland)
/
Query-to-communication lifting is a very useful tool for proving lower bounds and separations in communication complexity, circuit complexity, and proof complexity. However, one perceived drawback is that the bounds obtained through lifting are not very strong in terms of hidden constants. In this talk we discuss monotone circuit lower bounds for natural functions such as clique that not only match but improve previously known bounds. We do this by proving an extension to lifting theorems over non-binary alphabets.

Joint work with Susanna de Rezende.


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