Supercritical and Robust Trade-offs for Resolution Depth Versus Width and Weisfeiler–Leman

Speaker(s)

Shuo Pang

Affiliation

University of Copenhagen

Date

April 17, 2024, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

We give the first robust resolution trade-offs for which low width implies depth superlinear in the formula size. We show analogous results for the Weisfeiler–Leman algorithm, which also translate into trade-offs between number of variables and quantifier depth in first-order logic. Our main technical contribution is a new compression scheme and analysis of the so-called compressed Cop-Robber game introduced by [Grohe et al., FOCS 2023].

---