# Libor Barto Awarded ERC Synergy Grant

Mathematician Libor Barto from the Department of Algebra of CUNI MFF, together with Michael Pinsker from Vienna and Manuel Bodirsky from Dresden, won ERC grant to collaborate on research on the complexity of computing problems.

*The European Research Council’s* grants allow experts financial
independence and thus to create extraordinary conditions for delivering
excellent scientific research. Libor Barto with his colleagues received a so-called *Synergy
grant*, which requires interdisciplinary collaboration between
scientists with a high potential to bring about a breakthrough in their field.
The scientists will jointly explore the complexity of computational problems and
try, for example, to get closer to solving one of the seven mathematical
problems (millennium problems). The acronym of the grant is POCOCOP, i.e.
POlynomial — time COmputation: opening the blackboxes in COnstraint
Problems.

*"We're proceeding from a class of problems called CSP –
Constraint Satisfaction Problems, and we're going to expand that in three
directions: one way is approximation - looking for an
approximate solution, which may simplify the problem. Regarding our example, we
might try to divide people into ten groups, even though we know that there is a three-group division. The other direction is optimization –
looking for the ideal solution, in our example, so that as few enemies as
possible are together. The third direction is to infinite
fields, where the solution to the problem needs to be numbers - an
example is solving systems of linear equations or inequalities. To make the
research successful we must get to the heart of all directions, understand them
in greater depth and be able to connect them,"* says Barto,
who adds that while writing the grant application, they had already tested that
the collaboration would work.

*"Each of us contributed and brought original ideas. The resulting request is far better than any of us could have produced."*

*"As part of the new ERC project, we will seek to better
understand the complexity of the calculations. We want to know which problems
can be solved quickly on a computer and which can't. More specifically, we want
to approach a general theory that will explain why some problems are effectively
solvable and others are not,"* describes Libor Barto, adding that the
fundamental challenge is to understand and connect in depth several different,
hitherto quite distant directions of mathematics and computer
science.

*"This
is good news not only for Charles University, but for Czech science in general.
We can really congratulate ourselves, because with each ERC grant awarded, the
prestige of Czech scientific institutions increases internationally. The recent
success in raising funds for mathematical research is also underlined by the
extraordinary fact that Associate Professor Barto has already won a second ERC
grant for his scientific activities,"* stresses Charles University Rector
Prof. Milena Králíčková.

*OPMK, CUNI Press Release,
ForumPhoto: Eva Kořínková, Libor Barto's archive*