Theoretical Computer Science (TCS)

The theme is focused on fundamental questions on all aspects of the theory of computing. This includes current and potential applications.

The theme has a long-standing history and currently includes one of the world's biggest groups on Combinatorics on Words. Our members received funding from various bodies including EPSRC, Heilbronn, Leverhulme, in UK, FNRS, in Belgium, DFG, DAAD, Alexander von Humboldt, BMWI, BMBF, ITEA, in Germany, and ERC. The theme is currently engaged in various international projects including teams from MIT/US, NUS/ Singapore, ETH Zurich/ Switzerland, East China Normal University/ China, Porto/Portugal, Clermont-Ferrand/France, Milano/Italy, Liège/Belgium, Oxford/UK, Nancy/France, Saarbrücken and Göttingen/Germany, Akita/Japan, Istanbul/Turkey, Steering committee of WALNUT software, and groups like the EASI-Clouds (with many partners from France, Germany, Finland, Korea, Egypt), FAST, GreenPAD, CI3, in UK. Members of the theme are and have been members of different scientific committees including STACS, MFCS, WORDS, ICDT, ECOOP, ICSE, FSE, ASE, ICDCS, IPDPS.

Research Topics:

Our research covers a relatively wide range of established and emerging fields in Theoretical Computer Science, including:

  • Algorithms
  • Combinatorial optimisation
  • Combinatorics on words
  • Symmetric cryptography
  • Database theory
  • Distributed computing
  • Formal languages and automata theory
  • Formal methods
  • Game theory
  • Graph theory
  • Logic
  • Operations research
  • Scheduling
  • Symbolic dynamics
  • Foundations of algorithmic verification

Owen Bell (PhD research student)

Research interests:

Database Theory, Combinatorics on Words, Language-Theoretic Security, Learning Theory

Dr Joel Day (Lecturer)

Research interests:

Combinatorics on words, formal language theory, algorithms and computational complexity of string problems, string solvers and CSPs on words/strings.

Dr Shaheen Fatima (Senior Lecturer)

Research interests:

Multiagent systems, game theory, negotiation, artificial intelligence.

Dr Dominik Freydenberger (Senior Lecturer)

Research interests:

Database theory and finite model theory, combinatorics on words, formal language theory, learning theory.

Matthew Konefal (PhD research student)

Research interests:

Combinatorics of words and formal language theory; definability and decidability; compact language representations, especially word equations; algorithms for words.

Dr Robert Mercas (Senior Lecturer)

Research interests:

Algorithms and combinatorics on sequences, efficient algorithms and data structures, automata theory and formal languages.

Dr Lars Nagel (Lecturer)

Research interests:

Distributed algorithms, scheduling & load balancing, randomised algorithms. CS theory, storage systems, distributed systems.

Prof Iain Phillips

Research interests:

Internet Architectures: Routing and Performance Measurement. Ad-hoc networks, VANETs, swarm networking, WSNs. Bigdata and AI/machine learning

Dr Luca Prigioniero (Lecturer)

Research interests:

Formal language theory, automata theory, models of computation, descriptional complexity, reversibility in computations.

Professor Ana Salagean (Professor in Cryptography)

Research interests:

Symmetric cryptography (Boolean functions, functions over finite fields, sequences, feedback shift registers), finite fields, error-correcting codes (cyclic codes, codes over rings).

Dr Siani Smith (Lecturer)

Research interests:

Algorithmic graph theory.

Dr Markus Whiteland (Lecturer)

Research interests:

Combinatorics on words, automata theory in connection with numeration systems, foundations of software verification.

Dr Magdalena Zajaczkowska (Cyber Security Specialist)

Research interests:

Cyber security, AI.

Dr Chengyu Zhang (Lecturer)

Research interests:

Software engineering, programming Languages, formal Methods, artificial Intelligence
  • Foundations of the Finite Model Theory of Concatenation, EPSRC
  • Taming Extended Regular Expressions, DFG
  • Geometry in Robotics, Algorithms and Design (GRAnD), Loughborough University
  • Mathematical and Algorithmic Methods for Cryptographic functions and sequences, Royal Society Newton Mobility Grant, 2018-2023, PI Prof Ana Salagean and Prof Ferruh Ozbudak (METU and Sabanci University, Turkey)
  • Boolean functions with optimal stability of their cryptographic indicators under restriction of the inputs, EPSRC (EP/W03378X/1), 2023-2025, PI Prof Ana Salagean