Separating Rank Logic from Polynomial Time

Moritz Lichter

Type: Article

Publication Date: 2022-11-29

Citations: 6

DOI: https://doi.org/10.1145/3572918

View Publication

Locations

Journal of the ACM - View
arXiv (Cornell University) - View - PDF

Similar Works

Action	Title	Year	Authors
+	Separating Rank Logic from Polynomial Time	2021	Moritz Lichter
+ PDF Chat	Separating Rank Logic from Polynomial Time	2021	Moritz Lichter
+	Rank logic is dead, long live rank logic!	2015	Erich Grädel Wied Pakusa
+	Rank logic is dead, long live rank logic!	2015	Erich Grädel Wied Pakusa
+ PDF Chat	RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC!	2019	Erich Grädel Wied Pakusa
+	Approximations of Isomorphism and Logics with Linear-Algebraic Operators	2019	Anuj Dawar Erich Grädel Wied Pakusa
+ PDF Chat	Symmetric Circuits for Rank Logic	2021	Anuj Dawar Gregory Wilsenach
+	Choiceless Polynomial Time, Symmetric Circuits and Cai-Fürer-Immerman Graphs	2021	Benedikt Pago
+	Approximations of Isomorphism and Logics with Linear-Algebraic Operators	2019	Anuj Dawar Erich Grädel Wied Pakusa
+	Symmetric Circuits for Rank Logic	2018	Anuj Dawar Gregory Wilsenach
+	Symmetric Circuits for Rank Logic	2018	Anuj Dawar Gregory Wilsenach
+ PDF Chat	Finite Model Theory and Proof Complexity revisited: Distinguishing graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus	2022	Benedikt Pago
+	Finite Model Theory and Proof Complexity revisited: Distinguishing graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus	2022	Benedikt Pago
+	Choiceless Polynomial Time, Symmetric Circuits and Cai-Fürer-Immerman Graphs.	2021	Benedikt Pago
+	Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs	2018	Berit Grußien
+	Canonisation and Definability for Graphs of Bounded Rank Width	2019	Martin Grohe Daniel Neuen
+	Capturing Logarithmic Space and Polynomial Time on Chordal Claw-Free Graphs.	2018	Berit Grußien
+ PDF Chat	Canonisation and Definability for Graphs of Bounded Rank Width	2019	Martin Grohe Daniel Neuen
+ PDF Chat	Canonisation and Definability for Graphs of Bounded Rank Width	2022	Martin Grohe Daniel Neuen
+	Enumeration calculi and rank methods	1978	Tomáš Havránek

Works That Cite This (5)

Action	Title	Year	Authors
+ PDF Chat	Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements	2023	Martin Grohe Moritz Lichter Daniel Neuen Pascal Schweitzer
+ PDF Chat	Count-free Weisfeiler–Leman and group isomorphism	2024	Nathaniel A. Collins Michael Levet
+	Choiceless Polynomial Time, Symmetric Circuits and Cai-Fürer-Immerman Graphs.	2021	Benedikt Pago
+ PDF Chat	Limitations of the invertible-map equivalences	2022	Anuj Dawar Erich Grädel Moritz Lichter
+	Choiceless Polynomial Time with Witnessed Symmetric Choice	2024	Moritz Lichter Pascal Schweitzer

Works Cited by This (13)

Action	Title	Year	Authors
+ PDF Chat	Pebble Games with Algebraic Rules	2012	Anuj Dawar Bjarki Holm
+	Regular Graphs with Given Girth and Restricted Circuits	1963	H. Sachs
+	A new bound for the connectivity of cages	2012	C. Balbuena Julián Salas
+	On finite rigid structures	1996	Yuri Gurevich Saharon Shelah
+	Linear Diophantine Equations, Group CSPs, and Graph Isomorphism	2017	Christoph Berkholz Martin Grohe
+	Approximations of Isomorphism and Logics with Linear-Algebraic Operators	2019	Anuj Dawar Erich Grädel Wied Pakusa
+ PDF Chat	RANK LOGIC IS DEAD, LONG LIVE RANK LOGIC!	2019	Erich Grädel Wied Pakusa
+ PDF Chat	Canonisation and Definability for Graphs of Bounded Rank Width	2019	Martin Grohe Daniel Neuen
+ PDF Chat	Definability of linear equation systems over groups and rings	2013	Anuj Dawar Eryk Kopczyński Bjarki Holm Erich Grädel Wied Pakusa
+	Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time	2020	Moritz Lichter Pascal Schweitzer