Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps

DOI10.1145/2933575.2934560zbMath1394.03052arXiv1608.08704OpenAlexW2963494352MaRDI QIDQ4635882

Jakob Nordström, Christoph Berkholz

Publication date: 23 April 2018

Published in: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1608.08704

zbMATH Keywords

first-order logiclower boundstrade-offsWeisfeiler-Leman algorithmquantifier depthbounded-variable fragmentfirst-order counting logichardness condensationrefinement iterationsXORification

Mathematics Subject Classification ID

Logic in computer science (03B70) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Model theory of finite structures (03C13) Subsystems of classical logic (including intuitionistic logic) (03B20)

Related Items (4)

On space and depth in resolution ⋮ Tight lower and upper bounds for the complexity of canonical colour refinement ⋮ Upper Bounds on the Quantifier Depth for Graph Differentiation in First Order Logic ⋮ Supercritical Space-Width Trade-offs for Resolution

This page was built for publication: Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler--Leman Refinement Steps