Publications

2023

• 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},
  }