[Proof Complexity] MIAO seminar Mon Oct 6 at 14:00 CE(S)T with Bruno Pasqualotto Cavalar: Monotone circuit complexity of matching

[Jakob Nordström]

Dear all,

On Monday October 6 at 14:00, we will get the opportunity to listen to one of the most exciting pieces of news in theoretical computer science this year, namely what Bruno Pasqualotto Cavalar from the University of Oxford will tell us in his seminar titled "Monotone circuit complexity of matching". The abstract can be found 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/ . 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<mailto:jn at di.ku.dk>.

Best regards,
Jakob Nordström

**********

Monday Oct 6 at 14:00 on Zoom
Monotone circuit complexity of matching
(Bruno Pasqualotto Cavalar, University of Oxford)

We show that the perfect matching function on n-vertex graphs requires monotone circuits of size 2^{n^{Ω(1)}}. This improves on the n^{Ω(log n)} lower bound of Razborov (1985). Our proof uses the standard approximation method together with a new sunflower lemma for matchings.


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