- Research Staff
I am a postdoctoral research associate in the Logics and Algorithms group led by Anuj Dawar. My research interests revolve around logic and complexity. I especially enjoy to explore how methods from finite model theory can be used to prove lower bounds in other areas of theoretical computer science, such as proof complexity, algebraic complexity or the theory of constraint satisfaction problems.
One topic I am specifically interested in at the moment are the limitations of symmetric computation models and proof systems. This includes the logic Choiceless Polynomial Time as well as different kinds of symmetric circuit models.
I am also an associate of Robinson College.
Research
Descriptive Complexity
Finite Model Theory
Proof Complexity
Constraint Satisfaction Problems
Algebraic Complexity
Themes
Teaching
Course "The quest for a logic for polynomial time", held at the summer school ESSLLI 2025 in Bochum
Lecture 1: What is a logic for polynomial time?
Lecture 2: Fixed-point logics
Lecture 3: The Cai-Fürer-Immerman construction
Lecture 4: Linear-algebraic logics
Lecture 5: Choiceless Polynomial Time
Supervisions
- Lent 2025 & 2024: Computation Theory, Complexity Theory.
- Easter 2025 & 2024: Complexity Theory, Introduction to Probability
Past teaching at RWTH Aachen University, Germany
- Mathematical Logic (Summer terms 2022 and 2019)
- Mathematical Logic II (Winter term 2020)
- Seminar Logic, Complexity, Games: Propositional Proof Complexity
- Seminar Logic, Complexity, Games: Algorithmic Meta-Theorems and Parameterized Complexity
Publications
Selected talks
- Slides for the talk "Symmetric Proofs in the Ideal Proof System", held at the Proof Complexity 2025 Workshop, Oxford.
- Slides for the talk "Limitations of Affine CSP Algorithms", held at ICALP 2025, Aarhus.
- Slides for the talk "Symmetric Algebraic Circuits and Homomorphism Polynomials", held at AlMoTh 2025 (Bamberg) and at the FMT Workshop 2025 in Les Houches.
- Slides for the talk "Limitations of affine CSP Algorithms", held at CWC 2024, Colfosco.
- Slides for the talk "Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability", held at CSL 2024, Naples
- Slides for the talk "Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits", held at Highlights of Logic, Games and Automata, Kassel 2023
- Slides for the talk "A Finite-Model-Theoretic View on Propositional Proof Complexity", held at the Simons online workshop on Theoretical Foundations of SAT/SMT Solving, Berkeley 2021
Preprints
- Dawar, Pago, Seppelt, 2025. Symmetric Algebraic Circuits and Homomorphism Polynomials.
Arxiv: https://arxiv.org/abs/2502.06740
Conference proceedings
- Dawar, Grädel, Kullmann, Pago, MFCS 2025. Symmetric Proofs in the Ideal Proof System.
DOI: 10.4230/LIPIcs.MFCS.2025.40 - Lichter, Pago, ICALP 2025. Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems.
DOI: 10.4230/LIPIcs.ICALP.2025.166 - Lichter, Pago, Seppelt, CSL 2024. Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability.
DOI: 10.4230/LIPIcs.CSL.2024.36 - Pago, MFCS 2023. Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-circuits.
DOI: 10.4230/LIPIcs.MFCS.2023.73 - Pago, CSL 2023. Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus.
DOI: 10.4230/LIPIcs.CSL.2023.31 - Pago, CSL 2021. Choiceless Computation and Symmetry: Limitations of Definability.
DOI: 10.4230/LIPIcs.CSL.2021.33 - Grädel, Pago, Pakusa, CSL 2017. The Model-Theoretic Expressiveness of Propositional Proof Systems.
DOI: 10.4230/LIPIcs.CSL.2017.27
Journal articles
- Dawar, Pago, 2024. A Logic for P: Are we Nearly There Yet? ACM SIGLOG News, Vol. 11, Issue 2.
DOI: https://dl.acm.org/doi/10.1145/3665453.3665459 - Grädel, Grohe, Pago, Pakusa, 2019. A Finite-Model-Theoretic View on Propositional Proof Complexity. Logical Methods in Computer Science, Vol. 15, Issue 1.
DOI: https://doi.org/10.23638/LMCS-15(1:4)2019
Dissertation
Limitations of Choiceless Computation, 2023, RWTH Aachen University.
