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

Prelegent(ci)

Shuo Pang

Afiliacja

University of Copenhagen

Termin

17 kwietnia 2024 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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].

---