Open for all UnRAVeL Members: Research Seminar by RTG QuantLA: Computation in Finite Model Theory: Symmetric Algorithms and their Limitations

Tuesday, June 01, 2021, 1:00pm

Location: Online Session

Speaker: Benedikt Pago (RWTH Aachen)

 

Abstract: 

One of the central topics in finite model theory is the complexity of symmetric computation. From the point of view of “classical“ complexity theory, it might seem odd that symmetry should play a role at all in computation. In fact, if we consider Turing machines, it doesn’t. By contrast, from the perspective of logic, there are other natural ways to define computation models, and these are symmetry-invariant. Important examples are transitive-closure logic, fixed-point logic, and Choiceless Polynomial Time. In these frameworks, computations do not manipulate ordered binary strings, but unordered finite structures; for instance, graphs. The main  difference to Turing machines is that logics do not have the ability to choose arbitrary elements from the input but may only handle definable (isomorphism-invariant) subsets of the structure in each step. The study of symmetric computation models leads to a more fine-grained view on classical complexity classes such as PTIME because it brings the parameter “choice“ into the picture. This has a nice benefit: While it is generally hard to show the non-existence of efficient algorithms for a problem, in the symmetry-invariant setting we actually do have useful tools to prove lower bounds. These include pebble games and the analysis of automorphism groups. In this talk, I will give a general introduction to the subject and also present some of my own research on lower bounds for the logic Choiceless Polynomial Time.