Prefer a chat interface with context about you and your work?
Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps
We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of n-element structures that can be distinguished by a k-variable first-order sentence but where every such sentence requires quantifier depth at least nΩ(k / log k). Our trade-offs also apply to first-order counting …