Seminal
The magazine and atlas of EU-funded researchA new publication from the web and AI team at Scott Charnley

Atlas / Sweden

European Research Council grant · Running

META Meta-Computational Perspectives on Proof Complexity

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

OrganisationCityCountryRole
Lunds UniversitetLundSwedenCoordinator

Source: CORDIS, European Commission. Data of 5 Nov 2026, reused under the Commission's reuse policy. View on CORDIS · Grant DOI