Moritz Lichter | DeepAI

AI Chat

Featured Co-authors

Martin Grohe
52 publications
Pascal Schweitzer
24 publications
Daniel Neuen
21 publications
Anuj Dawar
20 publications
Erich Grädel
14 publications
Ilia Ponomarenko
12 publications
Tim Seppelt
7 publications
Benedikt Pago
5 publications
Gert Smolka
3 publications

∙ 08/23/2023

Compressing CFI Graphs and Lower Bounds for the Weisfeiler-Leman Refinements

The k-dimensional Weisfeiler-Leman (k-WL) algorithm is a simple combinat...

0 Martin Grohe, et al. ∙

∙ 08/10/2023

Limitations of Game Comonads via Homomorphism Indistinguishability

Abramsky, Dawar, and Wang (2017) introduced the pebbling comonad for k-v...

0 Moritz Lichter, et al. ∙

∙ 01/30/2023

The Iteration Number of the Weisfeiler-Leman Algorithm

We prove new upper and lower bounds on the number of iterations the k-di...

0 Martin Grohe, et al. ∙

∙ 10/14/2022

Witnessed Symmetric Choice and Interpretations in Fixed-Point Logic with Counting

At the core of the quest for a logic for PTime is a mismatch between alg...

0 Moritz Lichter, et al. ∙

∙ 05/27/2022

Choiceless Polynomial Time with Witnessed Symmetric Choice

We extend Choiceless Polynomial Time (CPT), the currently only remaining...

0 Moritz Lichter, et al. ∙

∙ 09/15/2021

Limitations of the Invertible-Map Equivalences

This note draws conclusions that arise by combining two recent papers, b...

0 Anuj Dawar, et al. ∙

∙ 04/27/2021

Separating Rank Logic from Polynomial Time

In the search for a logic capturing polynomial time the most promising c...

0 Moritz Lichter, et al. ∙

∙ 10/23/2020

Canonization for Bounded and Dihedral Color Classes in Choiceless Polynomial Time

In the quest for a logic capturing PTime the next natural classes of str...

0 Moritz Lichter, et al. ∙

∙ 05/08/2019

Walk refinement, walk logic, and the iteration number of the Weisfeiler-Leman algorithm

We show that the 2-dimensional Weisfeiler-Leman algorithm stabilizes n-v...

0 Moritz Lichter, et al. ∙

∙ 04/13/2018

Constructive Analysis of S1S and Büchi Automata

We study S1S and Büchi automata in the constructive type theory of the C...

0 Moritz Lichter, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world