Publications

2026

  1. STOC
    Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials
    Prateek Dwivedi, Benedikt Pago, and Tim Seppelt
    In STOC 2026
    (accepted for publication)
    DOI arXiv
  2. ITCS
    Symmetric Algebraic Circuits and Homomorphism Polynomials
    Anuj Dawar, Benedikt Pago, and Tim Seppelt
    In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)
    DOI arXiv
  3. CSL
    Arity hierarchies for quantifiers closed under partial polymorphisms
    Anuj Dawar, Lauri Hella, and Benedikt Pago
    In CSL 2026
    forthcoming
    DOI arXiv

2025

  1. ICALP
    Limitations of Affine Integer Relaxations for Solving Constraint Satisfaction Problems
    Moritz Lichter and Benedikt Pago
    In 52nd International Colloquium on Automata, Languages, and Programming, ICALP 2025, Aarhus, Denmark
    DOI arXiv
  2. MFCS
    Symmetric Proofs in the Ideal Proof System
    Anuj Dawar, Erich Grädel, Leon Kullmann, and Benedikt Pago
    In 50th International Symposium on Mathematical Foundations of Computer Science, MFCS 2025, Warsaw, Poland
    Invited for publication in special issue of Information & Computation
    DOI arXiv

2024

  1. ACM SIGLOG
    A Logic for P: Are we Nearly There Yet?
    Anuj Dawar and Benedikt Pago
    ACM SIGLOG News, Vol. 11, 2024
    DOI
  2. CSL
    Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability
    Moritz Lichter, Benedikt Pago, and Tim Seppelt
    In 32nd EACSL Annual Conference on Computer Science Logic, CSL 2024, Naples, Italy
    DOI arXiv

2023

  1. Limitations of Choiceless Computation
    Benedikt Pago
    RWTH Aachen University, Germany
    PhD thesis
    DOI
  2. CSL
    Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus
    Benedikt Pago
    In 31st EACSL Annual Conference on Computer Science Logic, CSL 2023, Warsaw, Poland
    DOI arXiv
  3. MFCS
    Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits
    Benedikt Pago
    In 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023, Bordeaux, France
    DOI arXiv

2021

  1. CSL
    Choiceless Computation and Symmetry: Limitations of Definability
    Benedikt Pago
    In 29th EACSL Annual Conference on Computer Science Logic, CSL 2021, Ljubljana, Slovenia
    DOI arXiv

2019

  1. LMCS
    A Finite-Model-Theoretic View on Propositional Proof Complexity
    Erich Grädel, Martin Grohe, Benedikt Pago, and Wied Pakusa
    Logical Methods in Computer Science
    DOI arXiv

2017

  1. CSL
    The Model-Theoretic Expressiveness of Propositional Proof Systems
    Erich Grädel, Benedikt Pago, and Wied Pakusa
    In 26th EACSL Annual Conference on Computer Science Logic, CSL 2017, Stockholm, Sweden
    DOI