Separating rank logic from polynomial time

DOI10.1145/3572918MaRDI QIDQ7032173zbMATH OpenFDO

Authors

Publication date 5 February 2025

Published in Journal of the ACM (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/3572918

zbMATH Keywords

CFI graphsinvertible-map gamelogic for PTimerank logic

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Descriptive complexity and finite models (68Q19)

Cites work

• A new bound for the connectivity of cages
• Affine systems of equations and counting infinitary logic
• An optimal lower bound on the number of variables for graph identification
• Approximations of isomorphism and logics with linear-algebraic operators
• Benchmark Graphs for Practical Graph Isomorphism
• Canonisation and Definability for Graphs of Bounded Rank Width
• Choiceless polynomial time
• Choiceless polynomial time on structures with small abelian colour classes
• Choiceless polynomial time, counting and the Cai-Fürer-Immerman graphs
• Definability of Cai-Fürer-Immerman Problems in Choiceless Polynomial Time
• Definability of linear equation systems over groups and rings
• scientific article; zbMATH DE number 686998 (Why is no real title available?)
• scientific article; zbMATH DE number 979011 (Why is no real title available?)
• scientific article; zbMATH DE number 1754602 (Why is no real title available?)
• Is polynomial time choiceless?
• Languages that Capture Complexity Classes
• Linear Diophantine Equations, Group CSPs, and Graph Isomorphism
• Logical hierarchies in PTIME
• On finite rigid structures
• On the theory of group codes
• Pebble games with algebraic rules
• Rank logic is dead, long live rank logic!
• Regular Graphs with Given Girth and Restricted Circuits
• Structure and complexity of relational queries

Cited in

(7)

• Limitations of game comonads for invertible-map equivalence via homomorphism indistinguishability
• Limits of symmetric computation (invited talk)
• Compressing CFI graphs and lower bounds for the Weisfeiler-Leman refinements
• Choiceless polynomial time with witnessed symmetric choice
• Linear algebraic quantifiers
• Computational complexity of the Weisfeiler-Leman dimension
• Computational complexity of the Weisfeiler-Leman dimension

This page was built for publication: Separating rank logic from polynomial time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7032173)