We are happy to present Moritz Lichter’s talk titled “Separating Rank Logic from Polynomial Time”.

The quest for a logic capturing polynomial time is the question whether there exists a logic that exactly defines all properties decidable in polynomial time. The most promising candidates for such a logic are Choiceless Polynomial Time (CPT) and rank logic. Rank logic extends fixed-point logic by a rank operator over prime fields. In this talk, I argue that rank logic cannot define the isomorphism problem of a variant of the so called CFI graphs. This isomorphism problem is decidable in polynomial time and actually definable in CPT. Thus, rank logic is separated from CPT and in particular from polynomial time.

Bio

Moritz completed his Bachelor in computer science at the TU Darmstadt before moving to Universität des Saarlands for his Master. Since 2017, Moritz is a PhD student supervised by Pascal Schweitzer (first at TU Kaiserslautern, then at TU Darmstadt), where his research is centered around polynomial time logic, graph isomorphism, descriptive complexity theory and computer algebra.