Fully-funded PhD scholarship in complex systems and simulation

The School of Computer Science at the University of St Andrews has a fully-funded scholarship available working within the Complex and Adaptive Systems Research Group with Prof Simon Dobson and Dr Peter Mann. Applications must be received by 1 March 2023.

Background

A “complex” system is one in which cause and effect can be hard to determine. In an epidemic, for example, it is easy to determine how someone was infected (by one of their social contacts), and we can also predict the overall size of an outbreak from the properties of the contact network — but we may not be able to predict in detail how the epidemic proceeds through the network, or what could be done to counter or steer it. Other examples include studying how rumours grow (and can be countered) on social networks, or to understand the effects of placement and error in sensor-driven systems such as those in climate science and ecology.

We understand relatively little about how things at “in-between” scales affect processes. These “meso-structures” include things like dense clusters of individuals, sparse chains of contacts, networks with core and periphery structures with different properties, and so on.

We are conducting a research programme investigating network meso-structures, with several goals. We want to understand these structures’ effects both analytically and numerically, meaning that we want to develop new frameworks for network process simulation and modelling based on our locally-developed simulation framework, epydemic, and to develop new analytic approaches to the study of these topics based on ideas from simplicial topology and sheaf theory.

Topics of interest

We are interested in a lot of different approaches, including but not limited to:

Applications of generating functions to the study of network processes
New applications of discrete combinatorial mathematics to complex systems
Understanding the effects of fine structure on processes
New simulation and numerical analysis techniques for complex systems
Epidemic spreading, especially the ways in which disease variants interact and develop through co-infection
Complex contagions such as rumour-spreading
Generating random networks with specific statistical properties

The scholarship

We have one fully-funded scholarship available, which will be awarded competitively to the best applicant. This scholarship covers all tuition fees and comes with a stipend (currently £17,668 full-time equivalent). Additional scholarships may be available from other sources.

The School welcomes applications from under-represented groups, and is willing to consider part-time and flexible registrations. The successful applicant will however be expected to conduct their research in St Andrews and not fully remotely.

To apply

Informal inquiries can be directed to Simon or Peter. Formal applications can be made through the School’s postgraduate research portal.

The deadline for applications is 1 March 2023.

A fully-funded, PhD position is now available at the AI research group

This fully-funded position will aim to improve both the modelling capabilities and the solving performance when confronting Automated Planning problems. We seek motivated candidates with a strong background in Computer Science, with excellent programming skills and some previous knowledge and experience in solving combinatorial optimisation problems.

Please take a look at the instructions on on how to apply.

The University of St Andrews is the top university in Scotland and second in the UK in The Times and Sunday Times Good University Guide 2023. Last year St Andrews was ranked number one in the UK, the first time in the near 30-year history of the Guide, or any UK ranking, that any university has been placed above those of Oxford and Cambridge.

If you are interested in either knowing more or have any informal enquiry, please do get in touch with Joan Espasa Arxer via email: jea20@st-andrews.ac.uk

The deadline for applications is the 1st of March 2023.

Fully funded PhD scholarship: Trustworthy Refactoring Tools for Haskell Programs

Supervisor: Dr Christopher Brown

Proposal and Context

Software is large and complex. Ubiquitous systems, such as weather forecasting, medical imaging, advanced AI and big-data processing are extremely expensive and time-consuming for software companies to produce. Moreover, they often comprise many subtle bugs that can have disastrous consequences, are difficult to find, and difficult or impossible to fix. What developers need are specialised software refactoring tools that help them develop these important and complex systems in a safe and semi-automated way, reducing developer time, human error and overall increasing productivity, saving companies and customers money, and providing robust, safe, systems that have been developed in a responsible and trustworthy way.

Refactoring is the process of changing the structure of software without changing what it does: in effect, refactoring is about helping the programmer re-purpose their code to make it more understandable, accessible, or amenable to further change in the program’s design. It is often a process that developers use on a daily basis by manually changing code to reflect an API change, re-purposing methods, eliminating duplicated code, remaining variable parameters and function names, generalising functions, etc. However, this process is rather tedious and cumbersome to apply manually: effecting a structural change that could potentially affect millions of lines of code across thousands of files is inevitably error – prone.

The advent of refactoring tool-support provides developers with automated transformations that they can apply to their code base, usually through an existing IDE interface. Refactoring tools, on the other hand, provide a way to apply refactorings across an entire code base in a semi-automatic way: they rely on the user to make certain choices about which refactorings to perform but are automatic in their underlying machinery. This automated underlying machinery means that both simple and complex refactorings can be applied to large code bases comprising thousands of files and millions of lines of code instantly.

However, automated tools are prone to bugs. This has the potentially disastrous consequence of a refactoring tool refactoring a program into one that contains subtle bugs or changes in behaviour. Despite the obvious implication that this will refactor software to contain, perhaps, subtle and difficult-to-spot bugs, it also erodes developers’ confidence in using refactoring —and general software tools— in general. Furthermore, a refactoring that introduces errors or is not trustworthy requires the programmer to inspect the transformed code, therefore taking out the benefit of using an automated tool in the first place. The problem is also amplified in that refactoring tools are extremely cumbersome, laborious and difficult in themselves to implement, especially over large programming languages, such as Haskell. This makes the refactorings deployed in such tools limited, both in number and applicability.

What is needed is to answer the following research questions:

How can we provide an automated approach of implementing refactoring tools, via compositionality and proof search?
How can we have the means to generate new refactorings easily that are safe and trusted by the developers that require them?
How can we provide a means to generate soundness proofs that the refactorings are safe and verified, in an automated way?

Exploratory Ideas

The PhD will be exploratory in nature. Here are some ideas for research directions to investigate as part of the PhD:

Formally characterise a number of refactorings for Haskell and prove properties of their general soundness.
Develop a fully verified refactoring tool that encodes general soundness proofs as part of its implementation using e.g., Dependent Types for the full Haskell standard.
Model a fully verified static and functional semantics for Haskell using e.g., Dependent Types.
Provide a fully generalised theory of the formalisation of refactoring tools for e.g., Haskell.
Provide an automated technique to find refactorings and proofs of refactorings, via e.g., proof search and compositionality of sub-proofs.
Evaluate the applicability of the approach on a number of use-cases and domains, from a variety of languages, across a different number of verticals.

Supervisor and Background

The PhD project is to be supervised by Dr Christopher Brown, a lecturer in the school of computer science who has over 18 years of experience working in the field of refactoring, program transformation and functional programming. Dr Brown contributed to the original HaRe (Haskell Refactorer) system, developed at the university of Kent, and has since developed a number of new refactoring tools for a variety of languages, including Haskell, Erlang and C/C++ for introducing and tuning parallel programs. Dr Brown also works in the field of formal semantics, with prior work on formalising refactorings and using types to reason about e.g., extra functional properties of imperative systems for embedded languages.

The PhD project fits directly with the research vision of the supervisor, who is also working on building refactoring tools for dependently typed languages, such as Idris and Pi-Forall.

The Programming Languages Research Group

The Programming Languages Research Group has a long history in functional programming and type theory. This project would directly fit with the group’s general vision of:

Making programming languages more accessible to experienced and inexperienced programmers alike.
Providing tool-support to make programming more accessible to inexperienced programmers.
Using types to formalise general soundness of programming language properties and semantics.
Providing verified refactoring tooling for functional programs.

To apply

Informal inquiries can be directed to Chris Brown. Formal applications can be made through the School’s postgraduate research portal.

The deadline for applications is 1 March 2023.

Phd Scholarships for 2023

Scholarship Description
The School of Computer Science is offering the following types of scholarships for 3.5 years of study in our PhD programme. UK, EU and International students are all eligible for:

• Fully funded scholarships consisting of tuition + stipend
• Tuition-only scholarships

This award is part-funded through the University’s new ‘handsels’ scheme.

Value of Award
• Tuition scholarships cover PhD fees irrespective of country of origin.
• Stipends are valued £17,668 per annum (or the standard UKRI stipend, if it is higher).

International applications are welcome. We especially encourage female applicants and underrepresented minorities to apply.

Application Deadline
All applications received before 1st February 2023 will be considered for the first round of scholarship eligibility. Later applications will also be considered for scholarships as long as funding remains.

How to Apply

If accepted, every PhD application indicating interest will automatically be considered for these scholarships. There is no need for a separate application.

The best way to win one of our scholarships is to make a robust PhD application. You are strongly encouraged to approach supervisors before formal submission to discuss your project ideas with them.

The School’s main groups are Artificial Intelligence and Symbolic Computation, Computer Systems and Networks, Human-Computer Interaction, and Programming Languages. It is highly recommended that applicants identify potential supervisors in their applications. A list of existing faculty and areas of research can be found at https://www.st-andrews.ac.uk/computer-science/prospective/pgr/supervisors/). All supervisors listed on this page may be contacted directly to discuss possible projects.

Full application instructions can be found at https://www.st-andrews.ac.uk/study/apply/postgraduate/research/.
Inquiries and questions may be directed to pg-admin-cs@st-andrews.ac.uk.

PhD Scholarships in Computer Science

Scholarship Description
The School of Computer Science is offering the following types of scholarships for 3.5 years of study in our PhD programme. All UK/EU and International students are eligible:

• Fully funded scholarships consisting of tuition + stipend
• Tuition-only scholarships

This award is part-funded through the University’s new ‘handsels’ scheme.

Value of Award
• Tuition scholarships cover PhD fees irrespective of country of origin.
• Stipends are valued £15,609 per annum.

Eligibility Criteria
We are looking for highly motivated research students willing to be part of a diverse and supportive research community. Applicants must hold a BSc or MSc in Computer Science or related area appropriate for their proposed topic of study.
International applications are welcome. We especially encourage female applicants and underrepresented minorities to apply.

Application Deadline
1st February 2022 for scholarship eligibility. Late applications will be considered as funding allows.

How to Apply
Every PhD application indicating interest, if accepted, will automatically be considered for these scholarships; there is no need for a separate application.
The best way to win one of our scholarships is to make a strong PhD application. You are also encouraged to approach supervisors before formal submission to discuss your project ideas with them.
The School’s main groups are Artificial Intelligence and Symbolic Computation, Computer Systems and Networks, Human-Computer Interaction, and Programming Languages. It is highly recommended that applicants identify potential supervisors in their applications. A list of existing faculty and areas of research can be found at https://www.st-andrews.ac.uk/computer-science/prospective/pgr/supervisors/).
Full application instructions can be found at https://www.st-andrews.ac.uk/study/apply/postgraduate/research/.
Inquiries and questions may be directed to pg-admin-cs@st-andrews.ac.uk.

Royal Television Society Bursary Scheme 2020

*STV has committed to provide a further ten students with RTS/STV bursary in the 2020/21 academic year.*

Considering a career in the broadcasting industry? Our students have successfuly secured Royal Television Society technology bursaries in 2019 and in previous years. The venture is intended to address a skills gap and attract some talented young people from top computer science or engineering courses to consider a career in television. Further details of the scheme can be found here: https://rts.org.uk/education-and-training-pages/bursaries

The RTS Bursary Scheme submission window opened on the 1st of February 2020 and will close on the 30th of June 2020.

Bursary recipients attend a summer tour of the industry, a financial award per year towards their studies, membership of the Royal Television Society and mentoring opportunities within their final year of study. Recipients are selected by a panel of industry professionals following an open call to UK students applying for courses at accredited colleges and universities.

St Andrews Research Open-day in Computer Science

Register for St Andrews ROCS HERE for free.

St Andrews ROCS is an event for those of you who engage (or are planning to engage) with research in the School of Computer Science at the University of St Andrews.

The main audiences are prospective postgraduate students, prospective or current industrial collaborators, and colleagues from other disciplines or Schools in Scotland and beyond.

The event will take place Friday October 26th 2018, between 10:00 AM and 4 PM.

There will be talks from all research groups, posters, demonstrations, guided tours, and much more.

You can learn about how to become a St Andrews PhD student or an active industrial collaborator.

The event will take place in the JACK COLE BUILDING, NORTH HAUGH, UNIVERSITY OF ST ANDREWS, ST ANDREWS, KY16 9SX, SCOTLAND.

You can download the programme of activities.

If you have any questions, e-mail dopgr-cs@st-andrews.ac.uk.

Register for St Andrews ROCS HERE for free.

Event details

When: 26th October 2018 10:00 - 16:00
Where: School of Computer Science
Format: Conference, Symposium, Visiting Day

Scholarships and bursaries: student perspectives and experiences

Applying to study at university includes many financial considerations. Scholarships and bursaries can help reward academic achievement and provide financial awards enabling students to undertake or further their education. Students in Computer Science have secured a variety of bursaries to help fund their passion for the subject. Successful undergraduate and postgraduate student perspectives are highlighted below.

Sherlock Cruz , the first recipient of The London Scholarship reflected on his time at St Andrews and how scholarships can transform lives. The scholarship encourages young students from the Greater London area to study at St Andrews by equipping them with accommodation and living costs.

The School is fortunate in receiving on-going support from Adobe for undergraduate students studying Computer Science by way of Adobe Prize Bursaries. Successful applicants receive an award each year for the duration of their degree.

Henry Hargreaves was the successful recipient of a Royal Television Society Technology Bursary. The bursary encourages the most talented Engineering and Computer Sciences undergraduates to consider a career in television.

Royal Television Society Bursary: Henry Hargreaves

Alice Herbison secured a Carnegie-Cameron Bursary to support postgraduate study enabling her to undertake our MSc in Human Computer Interaction.

Carnegie-Cameron Taught Postgraduate Bursaries 2013

Arkwright Awards for budding young engineers nurtures high-potential A-level and Scottish Advanced Higher students who have a desire to be future leaders in engineering disciplines, including computing, software, communications and product design. More information on Arkwright engineering awards and who can apply can be located on their website.

Arkwright Awards for budding young engineers

The scholarships and funding catalogue has up-to-date information on eligibility for undergraduate and postgraduate applicants.

Interdisciplinary PhD studentship available with Management

Dr Tristan Henderson has a St Leonards interdisciplinary PhD studentship available, to be co-supervised by Professor Kirstie Ball of the School of Management. The area of study is to do with ethical values and data science. The student will be part of CRISP (Centre for Research into Information, Surveillance & Privacy), a collaborative research centre involving St Andrews, Edinburgh and Stirling. As an interdisciplinary project, we welcome and will consider applications from students with a wide variety of backgrounds, from computer science to management to technology law and anything in between. More details can be found on the CRISP website.

n-Queens Completion is NP-Complete

Update, 2021

Over the years since we published this research, many people have approached us having solved the n queens puzzle, either for one n like 8 or 1000, or having written an algorithm to solve it for different sizes. Unfortunately this is not a major result in Computer Science and does not make one eligible to claim the $1M Clay prize. Many have been disappointed by this so we want to clarify why this is the case.

It is true that work on this problem could potentially result in the award but only if some exceptionally difficult conditions are met.

EITHER prove mathematically that NO possible algorithm could solve the n queens completion problem in polynomial time;

OR prove that there is an algorithm which is guaranteed to solve every instance of the n queens completion problem in polynomial time. Note that in this case the algorithm has to work on the completion version of the problem studied in our paper, not placing queens on an empty board; the algorithm has to give the correct answer on every possible instance given to it; and there has to be a mathematical proof that the algorithm’s runtime is bounded above by some polynomial in the size of the board. However fast a given algorithm runs when tested, this is not sufficient because there are an infinite number of possible tests available, so a mathematical proof is required.

AND in either case, prove this at a level that is published in a respected academic source and is widely accepted by research experts as correct.

We are delighted that our work has led so many people to be interested in the problem of solving problems like the n queens puzzle that fascinates us. But we also apologise for any impression we gave, unintentionally, that a solution to the n queens puzzle could lead to the award of the prize except under the extremely strenuous conditions listed above.

Ian Gent, 10 May 2021

Original Post from 2017:

Ian Gent, Christopher Jefferson and Peter Nightingale have shown that a classic chess puzzle is NP-Complete. Their paper “Complexity of n-Queens Completion” was published in the Journal of Artificial Intelligence Research on August 30, 2017.

The n-Queens puzzle is a classic chess problem: given a chessboard of size n by n, can you place n queens so that no two queens attack each other? That is, can you place the queens with no two queens are on the same row, column, or diagonal? The n-Queens puzzle has long been known to be simple to solve: you can solve the problem for all n except 2 and 3, and solutions for all other n can be described in a few lines. This very simplicity has led to repeated

controversy in Artificial Intelligence (AI). The n-Queens puzzle is often used as a benchmark problem, but good results on the problem can always be challenged because the problem is so simple to solve without using AI methods.

The new work follows a challenge on Facebook on New Year’s Day, 2015, when a friend of Ian’s asked him how hard n-Queens is if some queens were already placed on the board. It turns out, this version (dating from 1850) of the puzzle is only two years younger than the more famous n-Queens problem. The picture shows Peter (left) and Ian (right) with queens on the board at positions suggested by Nauck in 1850, the squares b4 and d5. Can you put another 6 queens on the board so that the entire board is a solution of 8-Queens? The general version with some number of queens preplaced on an n by n board is the n-Queens Completion puzzle.

With queens at b4 and d5, can you place 6 more queens to get a solution to the 8-queens puzzle? ©Stuart Nicol Photography, 2017

Ian, Christopher and Peter have shown that the n-Queens puzzle is in fact hard, not simple. It belongs to the complexity classes NP-Complete and #P-Complete. Other NP-Complete problems include the “travelling salesperson problem”, finding cliques in graphs, and many other important problems, from scheduling to circuit layout. This puts n-Queens Completion at the centre of the most important theoretical problem in computer science — it has long been known that either all NP-complete problems are easy, or none of them are. Most computer scientists believe that this means there is no efficient algorithm possible for solving this problem, compared to the very simple techniques long known for n-Queens.

The importance of this work is that it provides researchers with a benchmark that can be used for evaluating AI techniques. Moreover, it helps to explain why so many AI techniques have been used on the n-Queens puzzle. Most techniques do most of their work with some queens partially placed, using some form of (hopefully intelligent) trial and error. In fact it turns out that many researchers – in order to solve a simple problem – have solved it by turning the simple problem of n-Queens into the hard problem of n-Queens Completion.

It does seem that AI researchers should not use n-Queens as a benchmark, but the very closely related n-Queens Completion puzzle is a valid benchmark. As well as the theoretical results, the paper shows how example instances can be generated which appear to be hard in practice. Some caution is still needed, though. It does seem to be quite hard to generate hard instances of n-Queens Completion.

The University has also issued an article on the same paper, under the title “Simple” chess puzzle holds key to $1m prize

Computer Science Blog