[Proof Complexity] Seminar Mon May 17 at 14:00 CET with Kilian Risse: Average-case perfect matching lower bounds from hardness of Tseitin formulas

[Jakob Nordström]

Dear all,

On Monday May 17 at 14:00 CET we will have a seminar with Kilian Risse from KTH Royal Institute of Technology titled "Average-case perfect matching lower bounds from hardness of Tseitin formulas". Please see the abstract below for more details.

We will meet virtually 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://www.youtube.com/channel/UCN0G2Wfl9-sAKrVLVza7z4A for people who would like to hear the talk but cannot attend.

Most of our seminars consist of two parts: first a 50-55-minute regular talk, and then after a break a ca-1-hour in-depth technical presentation with (hopefully) a lot of interaction. The intention is that the first part of the seminar will give all listeners an overview of some exciting research results, and after the break people who have the time and interest will get an opportunity to really get into the technical details. (However, for those who feel that the first part was enough, it is perfectly fine to just discretely drop out during the break. No questions asked; no excuses needed.)

More information about upcoming video seminars can be found at http://www.csc.kth.se/~jakobn/videoseminars/ (an address that should change soonish, but for now it is what it is). In particular, please note that we also have a seminar this coming Monday May 10 at 14:00 CET with Noah Fleming from the University of Toronto titled "On the complexity of branch and cut".

If you do not wish to receive these announcements, or receive several copies of them, please send a message to jakob.nordstrom at cs.lth.se.

Best regards,
Jakob Nordström

**********

Monday May 17 at 14:00
Average-case perfect matching lower bounds from hardness of Tseitin formulas
(Kilian Risse, KTH Royal Institute of Technology)

We study the complexity of proving that a sparse random regular graph on an odd number of vertices does not have a perfect matching, and related problems involving each vertex being matched some pre-specified number of times. We show that this requires proofs of degree Ω(n / log n) in the Polynomial Calculus (over fields of characteristic ≠ 2) and Sum-of-Squares proof systems, and exponential size in the bounded-depth Frege proof system. This resolves a question by Razborov asking whether the Lovász-Schrijver proof system requires n^δ rounds to refute these formulas for some δ > 0. The results are obtained by a worst-case to average-case reduction of these formulas relying on a topological embedding theorem which may be of independent interest.

Joint work with with Per Austrin.


Jakob Nordström, Professor
University of Copenhagen and Lund University
Phone: +46 70 742 21 98
http://www.jakobnordstrom.se