Creating and sharing knowledge for telecommunications

Departamento de Matemática

Faculdade de Ciências e Tecnologia

Campus de Gambelas

8005-139 Faro

Portugal

Email: dgraca[at]ualg[dot]pt

- Assistant professor (with Habilitation) at the Departament of Mathematics, Faculty of Science and Technology at the University of Algarve.
- Member of the Security and Quantum Information Group at the Telecommunications Institute.

**Dynamical systems and computation****Computability questions related to the evolution of dynamical systems:**this is research on the limits of what can theoretically be inferred about dynamical systems using algorithms - it can be proved mathematically that some problems about dynamical systems cannot be solved with algorithms, no matter how clever the algorithms are or how many computational resources are used to run these algorithms.**Computational complexity questions related to the evolution of dynamical systems:**this is research on the limits of what can theoretically be inferred, using a reasonable amount of computational resources (time, etc.), about dynamical systems using algorithms. Some problems are "computationally intractable" in the sense that they are theoretically solvable, although in practice any algorithm solving them is so expensive from a computational point of view that the problem is in general "unsolvable" from a practical point of view. This is often due to the inherent "computational complexity" of the underlying problem. The idea is to try to understand which features these "untractable" problems have that distinguish them from "easier" problems. This is central question in the "P vs NP" millenium problem from the Clay Mathematics Institute.**Verification of properties involving dynamical systems:**in many applications one is interested in the following type of problem: to rigourously (i.e. using a mathematical sound approach) verify that some dynamical system is always "safe" (e.g. we may want to verify that an airplane will never fall due to a software problem, or that two trains will never collide) using a computational approach, since many systems are so complex that it is humanely impossible to verify them by "hand". Since some problems are not computationally solvable, in verification one is interested in understanding which properties can be automatically verified.

**Models of computation over continuous spaces****Computable analysis:**it studies mathematical analysis and continuous structures in general using a computability perspective, to understand which processes are computable. To achieve this objective continuous objects (real numbers, real functions, sets, etc.) are coded, for example, as infinite (Cauchy) sequences, etc., and computation is done over these sequences using a discrete (digital) model of computation.**Analog computation/Shannon's General Purpose Analog Computer (GPAC):**in this setting computation is done directly by a model of computation (the GPAC) introduced by Claude Shannon that uses ordinary differential equations to compute. This model can be implement in practice, for example, using analog electronics. Here we aim to understand what is the computational power of such models (compared to the digital paradigm) and whether such models are more well-suited for some tasks. We have for example shown that the GPAC can simulate Turing machines and that computable analysis are equivalent from a computability perspective and that the GPAC can simulate the standard model of discrete computation (Turing machines).**Polynomial ordinary differential equations as models of computation:**solutions of ordinary differential equations defined with the standard functions of analysis (polynomials, trigonometric functions, exponentials, etc.) can always be rewritten as solutions of polynomial ordinary differential equations. Here we are interested in understanding the computational power of such models which are equivalent to Shannon's GPAC.**Characterization of complexity classes using continuous models:**recently we were able to characterize classical (discrete) computational complexity classes such as P (from the "P vs NP" problem mentioned above) or PSPACE using a purely continuous characterization involving only polynomial ordinary differential equations. The idea here is trying to understand up to which point such characterizations can be made.

- Member of the Council of the Association Computability in Europe.
- Co-organizer of Days in Logic 2022.
- Co-organizer of the workshop CCC 2020: Continuity, Computability, Constructivity – From Logic to Algorithms. Other international events organized recently: CCC 2018, CCA 2016.
- Member of the Course Commission for the undergraduate degree in Informatics (Computer Science) at the University of Algarve.

- Editor (with Alex Simpson) of a special issue of the journal Logical Methods in Computer Science dedicated to the conferences "Continuity, Computability, Constructivity – From Logic to Algorithms (CCC 2019 and CCC 2020)".
- The special issue of the journal Logical Methods in Computer Science dedicated to the conference "Continuity, Computability, Constructivity – From Logic to Algorithms (CCC 2018)" was published.
- Best paper award (Track B) at the conference ICALP 2016.
- The PhD thesis of Amaury Pouly (PhD co-supervised with Olivier Bournez from Ecole Polytechnique, France) has been selected as the recipient of
**Ackermann Award**2017, by the European Association for Computer Science Logic.

- Computing with Infinite Data (Marie Curie RISE project financed via Horizon 2020 by the European Union). This projects involves 20 institutions from several countries.

- Full list of publications (includes preprints, when available).

© 2023, IT - Instituto de Telecomunicações | All Rights Reserved