Creating and sharing knowledge for telecommunications

Daniel Graça wins the ICALP 2016 Best Paper Award

by IT on 19-07-2016
Daniel Graça (IT in Lisbon), together with Olivier Bournez (LIX/École Polytechnique ) and Amaury Pouly (University of Oxford), received the International Colloquium on Automata, Languages, and Programming - ICALP 2016 Best Paper Award for "Polynomial Time corresponds to Solutions of Polynomial Ordinary Differential Equations of Polynomial Length".

Digital computers are essentially discrete machines, which use values like 0 or 1, without considering all the values in between. This paper shows that the problems which can be solved by computers using a reasonable amount of time (technically, problems in the class P) can be described exactly with purely continuous models (polynomial differential equations), where all values are allowed. According to Daniel Graça, “our result shows that it is possible to characterize digital computation with purely continuous models.”

The IT researcher revealed his satisfaction with the award, stating that “This prize was very important to us, since it acknowledges and recognizes the work we have been doing lately and validates our ideas. And, of course, it is always a very pleasant surprise to know that the scientific community is paying attention to the research we are doing.”