Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps
summary
Proves that for every k there exist n‑vertex relational structures that are k‑variable distinguishable but require quantifier rank at least n^{Ω(k / log k)}, nearly matching the trivial n^{k-1} upper bound. Proof combines XOR formulas encoded as isomorphism instances, high‑dimensional pyramid gadgets to force many pebble rounds, and Razborov’s hardness condensation to shrink variables without losing rounds; translates to equally large lower bounds on the number of Weisfeiler‑Leman refinement steps and impacts Babai‑style quasi‑polygraph‑isomorphism subroutines.
AI-written summary · about