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,
Photo: Eva Kořínková, Libor Barto's archive