Publications

2025

• A. Dawar, E. Grädel, L. Kullmann, and B. Pago. Symmetric Proofs in the Ideal Proof System. arXiv:2504.16820 [cs.LO], 2025.             
  BibTeX

  @misc{DGKP25,
       title = {Symmetric Proofs in the Ideal Proof System},
       author = {Anuj Dawar and Erich Gr{\"a}del and Leon Kullmann and Benedikt Pago},
       year = {2025},
       eprint = {2504.16820},
       archiveprefix = {arXiv},
       howpublished = {arXiv:2504.16820 [cs.LO]},
       primaryclass = {cs.LO},
       url = {https://arxiv.org/abs/2504.16820},
  }
  

2024

• M. Lichter, B. Pago, and T. Seppelt. Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability. In 32nd EACSL Annual Conference on Computer Science Logic (CSL 2024) (A. Murano and A. Silva, Eds.), vol. 288 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 36:1–36:19, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2024.             
  BibTeX

  @inproceedings{LPS24,
       author = {Moritz Lichter and Benedikt Pago and Tim Seppelt},
       title = {{Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability}},
       booktitle = {32nd EACSL Annual Conference on Computer Science Logic (CSL 2024)},
       pages = {36:1--36:19},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-95977-310-2},
       issn = {1868-8969},
       year = {2024},
       volume = {288},
       editor = {Aniello Murano and Alexandra Silva},
       publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
       address = {Dagstuhl, Germany},
       url = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2024.36},
       urn = {urn:nbn:de:0030-drops-196799},
       doi = {10.4230/LIPIcs.CSL.2024.36},
       annote = {Keywords: finite model theory, graph isomorphism, linear-algebraic logic, homomorphism indistinguishability, game comonads, invertible-map equivalence},
  }
  

2023

• M. Lichter, B. Pago, and T. Seppelt. Limitations of Game Comonads via Homomorphism Indistinguishability. arXiv:2308.05693 [cs.LO], full version of CSL'24 paper, 2023.             
  BibTeX

  @misc{LPS23,
       title = {Limitations of Game Comonads via Homomorphism Indistinguishability},
       author = {Moritz Lichter and Benedikt Pago and Tim Seppelt},
       year = {2023},
       howpublished = {arXiv:2308.05693 [cs.LO], full version of CSL'24 paper},
       url = {http://arxiv.org/abs/2308.05693},
  }
  

• B. Pago. Limitations of Choiceless Computation. PhD thesis, RWTH Aachen University, 2023.             
  BibTeX

  @phdthesis{BP23,
       author = {Benedikt Pago},
       title = {{Limitations of Choiceless Computation}},
       school = {{RWTH Aachen University}},
       year = {2023},
       url = {http://logic.rwth-aachen.de/pub/pago/diss.pdf},
  }
  

• B. Pago. Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits. arXiv:2302.05426 [cs.CC], full version of MFCS'23 paper, 2023.             
  BibTeX

  @misc{Pago23b,
       title = {Lower bounds for Choiceless Polynomial Time via Symmetric XOR-circuits},
       author = {Benedikt Pago},
       year = {2023},
       howpublished = {arXiv:2302.05426 [cs.CC], full version of MFCS'23 paper},
       url = {http://arxiv.org/abs/2302.05426},
  }
  

• B. Pago. Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) (J. Leroux, S. Lombardy, and D. Peleg, Eds.), vol. 272 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 73:1–73:15, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.             
  BibTeX

  @inproceedings{Pago23c,
       author = {Benedikt Pago},
       title = {{Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits}},
       booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
       pages = {73:1--73:15},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-95977-292-1},
       issn = {1868-8969},
       year = {2023},
       volume = {272},
       editor = {J\'{e}r\^{o}me Leroux and Sylvain Lombardy and David Peleg},
       publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
       address = {Dagstuhl, Germany},
       url = {https://drops.dagstuhl.de/opus/volltexte/2023/18607},
       urn = {urn:nbn:de:0030-drops-186077},
       doi = {10.4230/LIPIcs.MFCS.2023.73},
       annote = {Keywords: logic in computer science, finite model theory, descriptive complexity, symmetric computation, symmetric circuits, graph isomorphism},
  }
  

• B. Pago. Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus. In 31st EACSL Annual Conference on Computer Science Logic (CSL 2023) (B. Klin and E. Pimentel, Eds.), vol. 252 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 31:1–31:19, Dagstuhl, Germany. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2023.             
  BibTeX

  @inproceedings{Pago23,
       author = {Benedikt Pago},
       title = {{Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus}},
       booktitle = {31st EACSL Annual Conference on Computer Science Logic (CSL 2023)},
       pages = {31:1--31:19},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-95977-264-8},
       issn = {1868-8969},
       year = {2023},
       volume = {252},
       editor = {Bartek Klin and Elaine Pimentel},
       publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
       address = {Dagstuhl, Germany},
       url = {https://drops.dagstuhl.de/opus/volltexte/2023/17492},
       urn = {urn:nbn:de:0030-drops-174923},
       doi = {10.4230/LIPIcs.CSL.2023.31},
       annote = {Keywords: finite model theory, proof complexity, graph isomorphism},
  }
  

2022

• B. Pago. Finite Model Theory and Proof Complexity revisited: Distinguishing graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus. arXiv:2206.05086 [cs.LO], full version of CSL'23 paper, 2022.             
  BibTeX

  @misc{Pago22,
       title = {Finite Model Theory and Proof Complexity revisited: Distinguishing graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus},
       author = {Benedikt Pago},
       year = {2022},
       howpublished = {arXiv:2206.05086 [cs.LO], full version of CSL'23 paper},
       url = {http://arxiv.org/abs/2206.05086},
  }
  

2021

• B. Pago. Choiceless Computation and Symmetry: Limitations of Definability. In 29th EACSL Annual Conference on Computer Science Logic (CSL 2021) (C. Baier and J. Goubault-Larrecq, Eds.), vol. 183 of Leibniz International Proceedings in Informatics (LIPIcs), pp. 33:1–33:21, Dagstuhl, Germany. Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2021.             
  BibTeX

  @inproceedings{Pago21,
       author = {Benedikt Pago},
       title = {{Choiceless Computation and Symmetry: Limitations of Definability}},
       booktitle = {29th EACSL Annual Conference on Computer Science Logic (CSL 2021)},
       pages = {33:1--33:21},
       series = {Leibniz International Proceedings in Informatics (LIPIcs)},
       isbn = {978-3-95977-175-7},
       issn = {1868-8969},
       year = {2021},
       volume = {183},
       editor = {Christel Baier and Jean Goubault-Larrecq},
       publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
       address = {Dagstuhl, Germany},
       url = {https://drops.dagstuhl.de/opus/volltexte/2021/13467},
       urn = {urn:nbn:de:0030-drops-134673},
       doi = {10.4230/LIPIcs.CSL.2021.33},
       annote = {Keywords: finite model theory, descriptive complexity, choiceless computation, symmetries of combinatorial objects},
  }
  

2019

• E. Grädel, M. Grohe, B. Pago, and W. Pakusa. A Finite-Model-Theoretic View on Propositional Proof Complexity. Logical Methods in Computer Science, vol. Volume 15, Issue 1, 2019.             
  BibTeX

  @article{GGPW19,
       title = {{A Finite-Model-Theoretic View on Propositional Proof Complexity}},
       author = {Erich Gr{\"a}del and Martin Grohe and Benedikt Pago and Wied Pakusa},
       url = {https://lmcs.episciences.org/5119},
       doi = {},
       journal = {{Logical Methods in Computer Science}},
       volume = {{Volume 15, Issue 1}},
       year = {2019},
       month = {January},
  }
  

2017

• E. Grädel, B. Pago, and W. Pakusa. The Model-Theoretic Expressiveness of Propositional Proof Systems. In 26th EACSL Annual Conference on Computer Science Logic (CSL 2017), 2017.             
  BibTeX

  @inproceedings{GrPaPa17,
       author = {Erich Gr{\"a}del and Benedikt Pago and Wied Pakusa},
       title = {{The Model-Theoretic Expressiveness of Propositional Proof Systems}},
       url = {http://www.logic.rwth-aachen.de/pub/graedel/GrPaPa17.pdf},
       booktitle = {{26th EACSL Annual Conference on Computer Science Logic (CSL 2017)}},
       year = {2017},
  }