skip to content

Department of Computer Science and Technology

  • 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

Publications

Selected talks

Conference proceedings

  • Lichter, M., Pago, B. and Seppelt, T., 2024. Limitations of Game Comonads for Invertible-Map Equivalence via Homomorphism Indistinguishability Leibniz International Proceedings in Informatics, LIPIcs, v. 288
    Doi: 10.4230/LIPIcs.CSL.2024.36
  • Pago, B., 2023. Lower Bounds for Choiceless Polynomial Time via Symmetric XOR-Circuits Leibniz International Proceedings in Informatics, LIPIcs, v. 272
    Doi: 10.4230/LIPIcs.MFCS.2023.73
  • Pago, B., 2023. Finite Model Theory and Proof Complexity Revisited: Distinguishing Graphs in Choiceless Polynomial Time and the Extended Polynomial Calculus Leibniz International Proceedings in Informatics, LIPIcs, v. 252
    Doi: 10.4230/LIPIcs.CSL.2023.31
  • Pago, B., 2021. Choiceless computation and symmetry: Limitations of definability Leibniz International Proceedings in Informatics, LIPIcs, v. 183
    Doi: 10.4230/LIPIcs.CSL.2021.33
  • Grädel, E., Pago, B. and Pakusa, W., 2017. The model-theoretic expressiveness of propositional proof systems Leibniz International Proceedings in Informatics, LIPIcs, v. 82
    Doi: 10.4230/LIPIcs.CSL.2017.27
  • Journal articles

  • Dawar, A. and Pago, B., 2024. A Logic for P: Are we Nearly There Yet? ACM SIGLOG News, v. 11
    Doi: 10.1145/3665453.3665459
  • Grädel, E., Grohe, M., Pago, B. and Pakusa, W., 2019. A Finite-Model-Theoretic view on propositional proof Complexity Logical Methods in Computer Science, v. 15
    Doi: 10.23638/LMCS-15(1:4)2019
  • Theses / dissertations

  • Pago, B., 2023 (No publication date). Limitations of Choiceless Computation
  • Contact Details

    Room: 
    FE21
    Office address: 
    William Gates Building, 15 JJ Thomson Avenue, Cambridge CB3 0FD
    Email: 

    btp26@cam.ac.uk