LFCS Seminar: Tuesday 14 October: Bruno Cavalar Title: Monotone circuit complexity of matching Abstract We show that the perfect matching function on $n$-vertex graphsrequires monotone circuits of size $2^{n^{\Omega(1)}}$. Thisimproves on the $n^{\Omega(\log n)}$ lower bound of Razborov (1985).Our proof uses the standard approximation method together with a newsunflower lemma for matchings. Oct 14 2025 16.10 - 17.00 LFCS Seminar: Tuesday 14 October: Bruno Cavalar Bruno Cavalar University of Oxford https://brunopc.github.io/ IF G.03
LFCS Seminar: Tuesday 14 October: Bruno Cavalar Title: Monotone circuit complexity of matching Abstract We show that the perfect matching function on $n$-vertex graphsrequires monotone circuits of size $2^{n^{\Omega(1)}}$. Thisimproves on the $n^{\Omega(\log n)}$ lower bound of Razborov (1985).Our proof uses the standard approximation method together with a newsunflower lemma for matchings. Oct 14 2025 16.10 - 17.00 LFCS Seminar: Tuesday 14 October: Bruno Cavalar Bruno Cavalar University of Oxford https://brunopc.github.io/ IF G.03
Oct 14 2025 16.10 - 17.00 LFCS Seminar: Tuesday 14 October: Bruno Cavalar Bruno Cavalar University of Oxford https://brunopc.github.io/
