- Coordinator
- Lunds Universitet, Sweden
- Runs
- 1 January 2027 to 31 December 2031
- Status
- Running
- EU funding
- €1.5m
- Total cost
- €1.5m
- Partners
- 1 organisations in 1 countries
- Type
- European Research Council grant
- Grant agreement
- 101303903
What the project is doing
In the project's own words, from its summary on CORDIS.
Computational complexity theory seeks to understand the inherent difficulty of computational problems. For example, what is the fastest algorithm for factoring? Despite decades of progress, there are still problems—such as factoring—for which we lack efficient algorithms, and yet we cannot prove that they are intrinsically hard. Still, the assumption that factoring is indeed hard underpins much of modern cryptography and e-commerce.
This raises a fundamental question: Why are we unable to determine the resources required to solve many computational problems?This project addresses such meta-complexity questions—questions about the complexity of computational problems themselves—within the field of proof complexity. While similar questions in circuit complexity have led to major breakthroughs over the past decade, their counterparts in proof complexity remain largely unexplored.
I propose a systematic study of meta-complexity problems in proof complexity, with the overarching goal of explaining why current techniques fail to prove lower bounds for many natural formulas—even in weak proof systems. I aim to map the landscape of known lower bound methods, classify them by the complexity of their proofs of correctness, and push them to their theoretical limits. I also introduce two novel meta-complexity problems: encoding-independent lower bounds and the Minimum Proof Size Problem, both of which address notable gaps in the current literature.
By pursuing these goals, I seek to identify fundamental barriers and to guide future research in the field. Moreover, just as the study of the Minimum Circuit Size Problem has revealed deep connections to cryptography, learning theory, and derandomisation, a systematic investigation of analogous questions in proof complexity may uncover similar links to other areas. Ultimately, this project contributes to the broader aim of understanding the limits of efficient computation and efficient reasoning.
Topics
Who is involved
| Organisation | City | Country | Role |
|---|---|---|---|
| Lunds Universitet | Lund | Sweden | Coordinator |
Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI