Quantitative Logics and Complexity Theory

Logics are prominent in creating understanding of different computation paradigms, and as frameworks for the theory of verification and databases. The area of descriptive complexity theory uses logics to obtain machine independent characterisations of complexity classes, and logics like linear temporal logic are used in program verification to specify desired properties of runs of computations. Recently, many areas of computer science have taken a quantitative turn. The goal of this project is to study quantitative properties of systems by developing quantitative logics and related complexity theory. Please see http://www.virtema.fi/ for my recent works in this direction.

The concrete direction the student takes is flexible. One exciting direction is to develop the theory of quantitative hyperproperties which can express, e.g., fairness properties such as a request is granted in 75% of the time, and to study the related expressivity and complexity issues:

https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.60

https://dl.acm.org/doi/10.1145/3531130.3533360

Another direction is to develop logics for understanding the limitations of neural networks as an abstract computation device:

https://doi.org/10.48550/arXiv.2305.11833

https://arxiv.org/abs/2402.17805

Another direction is to study foundations of databases using logics over semiring annotated data:

https://arxiv.org/abs/2306.15516

Supervisor Bio

Dr. Virtema is an expert in the area of logic and complexity theory and has strong international collaborators. His recent works focus in the quantitative setting with applications to verification, database theory and neural networks.

About the Department & Research Group

Department of Computer Science: 99% of our research is rated in the highest two categories in the REF 2021, meaning it is classed as world-leading or internationally excellent. We are rated as 8th nationally for the quality of our research environment, showing that the Department of Computer Science is a vibrant and progressive place to undertake research.

You will join our Foundations of Computation (FOX) Group, whose research topics range from the theoretical mathematical foundations that underpin computer science to their applications in real world contexts. The FOX is one of the largest and most diverse research groups of its type in the UK. Please see https://www.sheffield.ac.uk/cs/research/groups/foundations-computation.

Candidate Requirements

Applicants should hold a very good degree (preferably a masters) in a relevant subject (i.e., Logic, Computer Science, or Mathematics). Candidates with exceptional undergraduate Honours degrees are considered. The project requires a good understanding of logic, and the willingness to learn the necessary mathematical background in computational complexity theory.

If English is not your first language, you must have an IELTS score of 6.5 overall, with no less than 6.0 in each component.

How to Apply

To apply for a PhD studentship, applications must be made directly to the University of Sheffield using the Postgraduate Online Application Form. Make sure you name Jonni Virtema as your proposed supervisor.

Information on what documents are required and a link to the application form can be found here – https://www.sheffield.ac.uk/postgraduate/phd/apply/applying

The form has comprehensive instructions for you to follow, and pop-up help is available.

Applications should include a research statement, CV, transcripts and two references.

The research statement (no longer than 4 A4 pages, including references) should outline your interests, the research direction you are interested in pursuing and include details of your skills and experience in logic and complexity theory.

Expected start date: February 2025