We prove new upper and lower bounds on the number of iterations the \(k\) -dimensional Weisfeiler-Leman algorithm ( \(k\) -WL) requires until stabilization. For \(k\geq 3\) , we show that \(k\) -WL stabilizes after at most \(O(kn^{k-1}\log n)\) iterations (where \(n\) denotes the number of vertices of the input structures), obtaining the first improvement over the trivial upper bound of \(n^{k}-1\) and extending a previous upper bound of \(O(n\log n)\) for \(k=2\) [Lichter et al., LICS 2019]. We complement our upper bounds by constructing \(k\) -ary relational structures on which \(k\) -WL requires at least \(n^{\Omega(k)}\) iterations to stabilize. This improves over a previous lower bound of \(n^{\Omega(k/\log k)}\) [Berkholz, Nordström, LICS 2016]. We also investigate tradeoffs between the dimension and the iteration number of WL, and show that \(d\) -WL, where \(d=\lceil\frac{3(k+1)}{2}\rceil\) , can simulate the \(k\) -WL algorithm using only \(O(k^{2}\cdot n^{\lfloor k/2\rfloor+1}\log n)\) many iterations, but still requires at least \(n^{\Omega(k)}\) iterations for any \(d\) (that is sufficiently smaller than \(n\) ). The number of iterations required by \(k\) -WL to distinguish two structures corresponds to the quantifier rank of a sentence distinguishing them in the \((k+1)\) -variable fragment \(\mathsf{C}_{k+1}\) of first-order logic with counting quantifiers. Hence, our results also imply new upper and lower bounds on the quantifier rank required in the logic \(\mathsf{C}_{k+1}\) , as well as tradeoffs between variable number and quantifier rank.

Martin Grohe

Moritz Lichter

Daniel Neuen

ACM Transactions on Computational Logic

TOCL 欢迎与计算机科学主题相关的逻辑各个方面的提交。该领域在计算机科学方面有着悠久的传统。获得 ACM 图灵奖的几位研究人员也为该领域做出了贡献，即 EDGAR CODD（关系数据库系统）、STEPHEN COOK（逻辑理论的复杂性）、EDSGER W. DIJKSTRA、ROBERT W. FLOYD、TONY HOARE、AMIR PNUELI、DANA SCOTT、EDMOND M. CLARKE、ALLEN E. EMERSON 和 JOSEPH SIFAKIS（程序逻辑、程序推导和验证、编程语言语义）、ROBIN MILNER（交互式定理证明、并发演算和函数式编程）和 JOHN MCCARTHY（函数式编程和人工智能中的逻辑）。逻辑在计算机科学中继续发挥重要作用，并已渗透到其多个领域，包括人工智能、计算复杂性、数据库系统和编程语言。本刊编委会寻求并希望吸引高- 在上述所有计算逻辑领域提交高质量的论文，使 TOCL 成为该领域的标准参考。理论和应用论文重新寻找。特别欢迎提交展示逻辑在计算机科学中的新颖使用的提交。

ACM Transactions on Computational Logic welcomes submissions on all aspects of logic related to computer science. This field has a long-standing tradition within computer science, with several Turing Award winners contributing significantly, including EDGAR CODD (relational database systems), STEPHEN COOK (complexity of logical theories), EDSGER W. DIJKSTRA, ROBERT W. FLOYD, TONY HOARE, AMIR PNUELI, DANA SCOTT, EDMOND M. CLARKE, ALLEN E. EMERSON, and JOSEPH SIFAKIS (program logic, program derivation and verification, semantics of programming languages), ROBIN MILNER (interactive theorem proving, concurrent calculi, and functional programming), and JOHN MCCARTHY (logic in functional programming and artificial intelligence). Logic continues to play a vital role in computer science and has permeated various fields, including artificial intelligence, computational complexity, database systems, and programming languages. The editorial board seeks to attract high-quality submissions in all areas of computational logic, aiming to make ACM Transactions on Computational Logic a standard reference in the field. We particularly welcome submissions that showcase novel uses of logic in computer science.

《ACM Transactions on Computational Logic》欢迎与计算机科学相关的逻辑各个方面的投稿。该领域在计算机科学中有着悠久的传统，许多获得ACM图灵奖的研究人员对其做出了重要贡献，包括EDGAR CODD（关系数据库系统）、STEPHEN COOK（逻辑理论的复杂性）、EDSGER W. DIJKSTRA、ROBERT W. FLOYD、TONY HOARE、AMIR PNUELI、DANA SCOTT、EDMOND M. CLARKE、ALLEN E. EMERSON和JOSEPH SIFAKIS（程序逻辑、程序推导和验证、编程语言语义）、ROBIN MILNER（交互式定理证明、并发演算和函数式编程）以及JOHN MCCARTHY（函数式编程和人工智能中的逻辑）。逻辑在计算机科学中继续发挥着重要作用，并已渗透到多个领域，包括人工智能、计算复杂性、数据库系统和编程语言。本刊编委会希望吸引在上述所有计算逻辑领域提交高质量论文，使《ACM Transactions on Computational Logic》成为该领域的标准参考。我们欢迎理论和应用论文的投稿，特别是那些展示逻辑在计算机科学中新颖应用的研究。

Category	Quartile
数学	4
数学, 计算机理论方法	4
数学, 逻辑学	4

The Iteration Number of the Weisfeiler-Leman Algorithm

ivySCI AI Smartly Parses PDF, Answers Researchers' Questions, and Helps You Understand Papers in Seconds

Journal Info