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.