Posted: 23rd August 2016

Standa Živný has been awarded a European Research Council (ERC) Starting Grant totalling over 1.4M euro over 5 years.

Standa's work on the Power of Algorithms in Discrete Optimisation project (PowAlgDO) is tackling one of the fundamental questions in algorithms: the power of convex relaxations.

Convex relaxations, such as linear and semidefinite programming, constitute one of the most powerful techniques for designing efficient algorithms, and have been studied in theoretical computer science, operational research, and applied mathematics. Standa and his team seek to establish the power convex relaxations through the lens of, and with the extensions of methods designed for, Constraint Satisfaction Problems (CSPs).

The project's goal is twofold. First, to provide precise characterisations of the applicability of convex relaxations such as which problems can be solved by linear programming relaxations. Secondly, to derive computational complexity consequences such as for which classes of problems the considered algorithms are optimal in that they solve optimally everything that can be solved in polynomial time.

The European Research Council (ERC), set up by the European Union in 2007, is described as the 'first European funding organisation for excellent frontier research.' In first eight years since its foundation, the ERC awarded 5,000 research grants, worth €9 billion, to scientists of 66 nationalities. In 2016, the ERC will fund projects worth a further  €1.7 billion. This includes Starting Grants are awarded to researchers with no more than seven years of post-doctoral experience, who can use the money to set up their own research teams.