Theoretical Computer Science

This area explores the fundamental and foundational aspects of computers and computation. Aiming to improve understanding of computation and its capabilities, limitations and future potential, this research area encompasses research around logic and semantics, and the study of algorithms, complexity and automata; researchers employ abstract models, formal and rigorous methods, logical concepts and semantics, among other approaches. Formed by merging the Theory of Computation and Maths of Computing research areas, this fundamental research area underpins much of the broader computer science field and has strong links with several branches of mathematics (e.g. logic, algorithms, combinatorics and numerical analysis). 

We aim to maintain this research area as a proportion of the EPSRC portfolio. Theoretical Computer Science is an underpinning area with potential for transformative long-term impacts. Our strategy reflects the need to preserve its long-term health in the UK and that of the areas it underpins.

By the end of the current Delivery Plan period, we aim to have:

  • A diverse area that includes foundational, theoretical research and novel Theoretical Computer Science being applied to real problems, and shows evidence of long-term research impacts
  • An area which reflects the UK's well-established standing and leadership in formal methods, semantics and related subjects
  • Greater use of classical algorithmic techniques across computer science, incorporating fundamental mathematics and work on the study of computation and related subjects, to build UK capability while maintaining the current strength of Theoretical Computer Science activity
  • Strong leadership within the community working on Theoretical Computer Science to ensure existing UK excellence is preserved over the long term, and provide specialist capability to address strategic priorities such as the growing need for safe, secure Information and Communication Technologies (ICT). Researchers should reflect on how they can address the challenges described in EPSRC's Safe and Secure ICT priority
  • Continued engagement between researchers and industrial partners, to test and prove the application of research to real or realistic problems

Researchers should exploit opportunities to work across discipline boundaries, ground their research in emerging computational paradigms and architectures, and maintain strong links with areas underpinned by Theoretical Computer Science (Verification and Correctness, Architectures and Operating Systems, Programming Languages and Compilers etc.).

Over the current Delivery Plan, it is expected that researchers will build a stronger interface with mathematics in areas such as logic and combinatorics. This provides an opportunity for researchers to contribute to EPSRC's Cross-Disciplinarity and Co-Creation priority.

Highlights:

Theoretical Computer Science is a fundamental research area with potential for high-impact, transformative research over the long-term, especially through links to related fields such as cryptography, machine learning, verification, security, data science, quantum computing and the Internet of Things (IoT) (Evidence source 1,2,3,4).

It also underpins many areas of the UK ICT research landscape and has been identified as particularly important for the long-term health of the Architecture and Operating Systems, Verification and Correctness, and Programming Languages and Compilers research areas by their respective communities (Evidence source 5).

The UK does world-leading research in many aspects of Theoretical Computer Science (Evidence source 1,2), evidenced by a strong UK presence at major international conferences. The UK is particularly strong in areas such as logic-based approaches, semantics and formal methods (Evidence source 1). Research around algorithms and complexity in the UK is limited to a few pockets of exceptional research (Evidence source 1,2). The Alan Turing Institute is expected to influence the wider UK Theoretical Computer Science research landscape through its focus on foundational and translational research to support data science (Evidence source 6).

Theoretical Computer Science in the UK has many industrial partners across a range of sectors, demonstrating that UK research in this area is considered to contribute to impact (Evidence source 1,2). These partnerships enable trialling and testing of research developments in an industrial context and present opportunities for knowledge transfer as well as for spinout companies.

Although the number of researchers is good, leadership is focused on a small number of fellowships and programme grants (Evidence source 5). Programme grants are considered vital for addressing strategic priorities in this area as they bring together exceptional expertise (Evidence source 1,2).

This research area is expected to contribute particularly to the EPSRC Connected and Resilient Nation Outcomes, and especially the following Ambitions:

C1: Enable a competitive, data-driven economy

Researchers can contribute to optimisation and financial technology, and develop novel algorithmic techniques to support data analytics. Theoretical Computer Science can work with the Alan Turing Institute to identify grand challenges.

C2: Achieve transformational development and use of the Internet of Things

Researchers can contribute by developing new approaches to data analytics, data processing and data security in collaboration with the IoT Research Hub.

C3: Deliver intelligent technologies and systems

Researchers can develop a foundation of new mathematical sciences and computer science to underpin the development of smart tools and technologies.

C4: Ensure a safe and trusted cyber society

Researchers can contribute with foundational work (e.g. defining new models of data processing and interchange incorporating security by design).

R3: Develop better solutions to acute threats: cyber, defence, financial and health

Researchers can develop improved solutions to cyber threats, support decision-making across complex systems and underpin encryption and privacy technologies.

  1. Community and user engagement (individual input, group feedback, team visits/events and evidence-gathering activities).
  2. Input from the ICT Strategic Advisory Team (SAT), the Maths SAT, the UK Computer Research Council (UKCRC) Executive Committee and Research Excellence Framework (REF) 2014 panellists.
  3. National Audit Office (NAO), The UK Cyber Security Strategy: Landscape Review (PDF), (2013)
  4. EPSRC, Healthcare Technologies Grand Challenges Report (PDF), (2014).
  5. Analysis of EPSRC data (grant data, application statistics, portfolio funding landscape).
  6. The Alan Turing Institute, Shaping our Strategy (PDF), (2016).

Research area connections

This diagram shows the top 10 connections between Research Areas within the EPSRC research portfolio. The depth of the segment relates to value of grants and the width of the segment relates to the number of grants shared by those two Research Areas. Please click to see the related Research Area rationale.

Maintain

We aim to maintain this area as a proportion of the EPSRC portfolio.

Visualising our Portfolio (VoP)
Visualising our portfolio (VoP) is a tool for users to visually interact with the EPSRC portfolio and data relationships.

EPSRC support by research area in Theoretical computer science (GoW)
Search EPSRC's research and training grants.

Contact Details

In the following table, contact information relevant to the page. The first column is for visual reference only. Data is in the right column.

Name: Rhys Perry
Job title: Portfolio Manager
Department: ICT
Organisation: EPSRC
Telephone: 01793 444466