Professor Standa Zivny, a Tutor in Computer Science at Jesus College, has been awarded a five-year €2M ERC Consolidator Grant NAASP: New Approaches to Approximability of Satistfiable Problems.

Standa is one of 313 scientists to have been given an award from the €632m EU investment for mid-career researchers across all areas, and the only one from Oxford University in this round.

Standa’s research centres around the application of mathematics to the design and analysis of algorithms. The ERC Consolidator Grant, which runs from 2022 until 2027, will enable him to hire 3 postdoctoral researchers for the duration of the grant, as well as provide funding for research visits, to tackle the problem of understanding the computational complexity of satisfiable constraint satisfaction problems (CSPs). A classic example is the approximate graph colouring problem, whose complexity is still open despite sustained effort since the 1970s. A very recent line of work on promise CSPs proposed a framework for studying such problems under one umbrella and initiated the first steps. The goal of this project is to unleash the full power of the new framework: to develop novel approaches for proving hardness, to devise new algorithmic paradigms, and to attack major open problems.

ERC grants are highly competitive. Standa says, “The ERC Consolidator Grant provides me with long-term funding to pursue high-risk, ground-breaking ideas in basic research. I am delighted and honoured to have been given the opportunity to continue my work on answering fundamental questions about the nature of efficient computation”.

NAASP is the second ERC Grant awarded to Standa; from 2017 to 2022 he held the ERC Starting Grant PowAlgDO (Power of Algorithms in Discrete Optimisation).