Benedikt Pago
University of Cambridge, Robinson College. Logics and Algorithms Group.
I am a Postdoctoral Research Associate at Robinson College in Cambridge. As a theoretical computer scientist, I am part of the Logic and Algorithms group led by Anuj Dawar. Before that, in 2023, I completed my PhD under the supervision of Erich Grädel at RWTH Aachen University, Germany.
My research interests cover a range of topics in complexity theory and logic, such as descriptive complexity and finite model theory, proof complexity, algebraic circuit complexity, and the theory of constraint satisfaction problems.
The central question that is studied in these areas is what amount of resources, say, computing time, circuit size, number of lines in a proof, or number of variables in a logical formula, is required to solve a given problem, express a query, or prove a mathematical statement.
I am especially interested in proving lower bounds by building a comprehensive theory that ties all these facets of complexity together and explains what it is that makes a particular problem easy or hard. Its overarching framework is based on the notion of symmetry that crops up in different guises in circuits, proofs, or algorithms.
News
| Mar 02, 2026 | Looking forward to the annual meeting of the Algorithmic Model Theory community AlMoTh 2026, which is happening in Passau this year. |
|---|---|
| | |
| Feb 23, 2026 | Upcoming trip to Paris for CSL 2026. I’ll be speaking about Arity hierarchies for quantifiers closed under partial polymorphisms, my new paper together with Anuj Dawar and Lauri Hella that explores a new perspective on finite model theory inspired by methods from the world of constraint satisfaction (CSP). |
| | |
| Feb 02, 2026 | Our brand-new paper Lower Bounds in Algebraic Complexity via Symmetry and Homomorphism Polynomials with Prateek Dwivedi and Tim Seppelt has just been accepted at STOC 2026! Building on the framework from our recent ITCS’26 paper, we solve the long-standing open problem of separating the algebraic complexity classes VF, VBP, and VP – with restriction to symmetric circuits, at least… |
| | |
| Jan 27, 2026 | Excited for ITCS 2026 in Milan featuring our new paper Symmetric Algebraic Circuits and Homomorphism Polynomials with Anuj Dawar and Tim Seppelt. We give a surprising graph-theoretic characterisation of all polynomials computable by efficient symmetric circuits. Check out our video talk! |
| | |
| Sep 22, 2025 | CSP World Congress 2025 |
| | |