Ján Pich awarded ERC Consolidator Grant for research into proof complexity

Senior Researcher Ján Pich has been awarded a prestigious European Research Council (ERC) Consolidator Grant for his project ProCom, which tackles foundational questions in computational complexity and mathematical logic. 

Ján is one of only five researchers at Oxford – and among just 11.2% of applicants Europe-wide – to receive funding in this highly competitive call. Consolidator Grants support outstanding mid-career researchers in building research teams and advancing ambitious scientific ideas. The awards are funded by the EU’s Horizon Europe programme and provide around €2 million over five years. 

These ERC awards recognise exceptional ambition and talent. Each project has the potential to deepen scientific understanding and deliver tangible benefits for society – from biodiversity and climate resilience to sustainable technologies and advanced chemistry. Prof James (Jim) Naismith, Head of the Mathematical, Physical, and Life Sciences Division (MPLS)

ProCom (Proof complexity of circuit lower bounds)   

ProCom tackles a fundamental question in mathematics and computer science: are there explicit problems that are formally hard to solve? In other words, can we prove that certain mathematical questions, by their nature, will never have efficient solutions?  

Such questions can be investigated in the language of mathematical logic and complexity theory. Surprisingly, they have turned out to be extremely difficult and the flagship problem in the area, the P vs NP problem, has become notorious for that reason. It asks whether every problem whose solution can be verified quickly can also be solved quickly.   

In recent years, new meta-mathematical theory surrounding the P vs NP problem has emerged. The ProCom project aims to uncover its full potential. 

I am fascinated by the possibility of the existence of a simple algorithm automating (perhaps even without using a computer) difficult tasks such as proving mathematical theorems and shedding light on the very nature of creativity. Dr Ján Pich