Computer Science: Fully Funded EPSRC and Swansea University PhD Scholarship: Robust Reachability Problems for Linear Dynamical Systems

Funding providers: Engineering and Physical Sciences Research Council (EPSRC) and Swansea University's Faculty of Science and Engineering

Subject areas: Computer Science

Project start date: 

• 1 October 2022 (Enrolment open from mid-September)

Project supervisors: Dr Eike Neumann and Dr Ulrich Berger

Aligned programme of study: PhD in Computer Science

Mode of study: Full-time or part-time (at least 0.5 FTE)

Project description: 

The aim of this project is to advance our understanding of fundamental computational problems concerning the long-term behaviour of linear dynamical systems.

Linear dynamical systems constitute natural descriptions of the evolution of a wide range of real-world systems that appear in physics, biology, economics, and other natural sciences. In computer science, they arise in connection with questions such as loop termination, model checking, and probabilistic or quantum computation.

Decision problems for dynamical systems have a long history in theoretical computer science, reaching back at least to the mid-1970s.

The vast majority of the existing computer science literature on reachability problems begins with the assumption that the dynamical systems under consideration are given by exact algebraic or rational data.

In applications in the sciences and engineering, this assumption is frequently violated, since the parameters of the systems under consideration may involve fundamental physical constants, come from measurements, or involve other sources of inexactness or uncertainty. Moreover, reachability problems over rational data become undecidable or provably "hard" already for seemingly very simple systems.

In this project, the focus is shifted to dynamical systems which are defined using arbitrary real numbers. The formal framework for this is the bit-model of real computation, where real numbers are encoded as second-order objects. This approach allows us to incorporate transcendental and inexact data, while at the same time avoiding the aforementioned undecidability and hardness results.

A particular emphasis will be placed on computability and complexity of positivity and inequality problems for univariate holonomic functions or sequences.

The project is suitable for students with a background in (theoretical) computer science or mathematics. The student will employ a synthesis of numerical and symbolic methods, combining tools from computability, computational complexity, analysis (differential equations, analytic number theory), topology, and algebra (real algebraic geometry, quantifier elimination). Prior knowledge or experience in one or more of these areas are desirable, but not strictly necessary.

Eligibility

Candidates must normally hold an undergraduate degree at 2.1 level in Computer Science, Mathematics or a closely related discipline, or an appropriate master’s degree with a minimum overall grade at ‘Merit’ (or Non-UK equivalent as defined by Swansea University).

English Language requirements: If applicable – IELTS 6.5 overall (with at least 6.0 in each individual component) or Swansea recognised equivalent.

This scholarship is open to candidates of any nationality.

For more information, including how to apply, please visit:

https://www.swansea.ac.uk/postgraduate/scholarships/research/computer-science-epsrc-su-phd-robust-2022-rs122.php