MIAO/BARC talk by Duri Janett
Tuesday, March 4, 2025, Duri Janett, PhD student with MIAO at the University of Copenhagen, will give a talk on "Truly Supercritical Trade-offs for Resolution, Cutting Planes, Monotone Circuits, and Weisfeiler–Leman".
Abstract:
We exhibit supercritical trade-off for monotone circuits, showing that there are functions computable by small circuits for which any circuit must have depth super-linear or even super-polynomial in the number of variables, far exceeding the linear worst-case upper bound. We obtain similar trade-offs in proof complexity, where we establish the first size-depth trade-offs for cutting planes and resolution that are truly supercritical, i.e., in terms of formula size rather than number of variables, and we also show supercritical trade-offs between width and size for treelike resolution.
Our results build on a new supercritical depth-width trade-off for resolution, obtained by refining and strengthening the compression scheme for the Cop-Robber game in [Grohe, Lichter, Neuen & Schweitzer 2023]. This yields robust supercritical trade-offs for dimension versus iteration number in the Weisfeiler–Leman algorithm. Our other results follow from improved lifting theorems that might be of independent interest.
In the second (blackboard) part of the talk, we will focus on the proof of the depth-width trade-off. In particular, we will describe a strategy for the Robber in the compressed Cop-Robber game, which corresponds to the depth lower bound in the small width regime.
This is joint work with Susanna F. de Rezende, Noah Fleming, Jakob Nordström and Shuo Pang.
----------------------
Most of the MIAO 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 a self-contained 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 the MIAO seminar series can be found at https://jakobnordstrom.se/miao-seminars/ .
----------------------
Bio:
Duri Andrea Janett is a second year PhD student at the University of Copenhagen and Lund University, advised by Jakob Nordström and a member of the MIAO group. His interests are in computational complexity theory, and in particular proof complexity. Before coming to Copenhagen, Duri received a Bachelor’s and Master’s degree in mathematics from ETH Zürich, where he was advised by Carola Doerr and Johannes Lengler.