BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Monotone Circuit Complexity of Matching - Bruno Cavalar (Oxford)
DTSTART:20251007T130000Z
DTEND:20251007T140000Z
UID:TALK234901@talks.cam.ac.uk
CONTACT:Tom Gur
DESCRIPTION:We show that the perfect matching function on $n$-vertex graph
 s requires monotone circuits of size $2^{n^{\\Omega(1)}}$. This improves o
 n the $n^{\\Omega(\\log n)}$ lower bound of Razborov (1985). Our proof use
 s the standard approximation method together with a new sunflower lemma fo
 r matchings.
LOCATION:Computer Laboratory\, William Gates Building\, Room SS03
END:VEVENT
END:VCALENDAR