ERCIM has selected Paweł Parys from the University of Warsaw as the winner of the 2012 Cor Baayen Award for a promising young researcher in computer science and applied mathematics. In a tight competition Paweł Parys was chosen from 21 excellent candidates from all over Europe as an exceptionally gifted young researcher.
Paweł’s main fields of interest are algorithms and computation theory. In his young career, Paweł’s research has already led to two extraordinary results in very different fields such as linear time evaluation of XPath and higher-order pushdown automata.
The XPath (a language for addressing parts of an XML document) evaluation problem is important in practice, in particular for the performance of Web browsers which generally include XPath evaluators. These evaluators are often quite inefficient, in many cases running in exponential time (in relation to the size of the query). In his groundbreaking work, Paweł devised a system for evaluation of XPath in time linear in the size of the document. Until recently, this was widely believed to be impossible. The improvement is dramatic for XML documents with billions of nodes, such as the DBLP database, for example.
In his research on higher-order pushdown automata, Paweł could prove that collapse increases the power of higher-order pushdown automata, which was a major open problem (pushdown automata are used for instance in theories about what can be computed by machines). Higher-order pushdown automata are like pushdown automata, except that they can use stacks of stacks, or stacks of stacks of stacks, and so on. They appear naturally when modelling the behaviour of recursive higher-order programs in functional languages. The question “does a recursive higher-order program behave correctly for all possible inputs?” can be recast as a question about the language accepted by a deterministic higher-order pushdown automaton. One of the most important open problems in this area was about the equivalence of two models: deterministic higher-order pushdown automata, and deterministic higher-order pushdown automata with the so-called collapse operation. It has been conjectured that the collapse operation gives more power to the automata. In a series of papers, including two STACS papers and a paper accepted to LICS 2012, Paweł Parys has proved this conjecture. This settles an important, and technically difficult, open problem.
Although Paweł Parys has just finished his PhD in January 2012, is work has already been recognized with best student paper award at PODS 2009 (the top database theory conference), the Witold Lipski Prize for Young Researchers in Computer Science 2011(an award for the best young Polish computer scientist. He was also the recipient of a "Start" stipend for young researchers awarded by the Foundation for Polish Science in 2012 as well as several achievements in programming competitions.
For more information about the ERCIM Cor Baayen Award, see http://www.ercim.eu/activity/cor-baayen-award
The finalists in the 2012 competition were (in alphabetical order):
George Alexandropoulos
Xavier Allamigeon
Panayiotis Andreou
Tobias Berka
Antonis Bikakis
Aristodemos Cleanthous
Anthony Cleve
Marco D'Ambros
Stanley Durrleman
Jan Hamaekers
Razvan Ionasec
Attila Kertesz
Lars Lydersen
Frans Oliehoek
Theodore Patkos
Nico Pietroni
Katharina Reinecke
Nikolaos Stamatopoulos
Petra Sundström
Nedeljko Vasic