Approximation of Constraint Satisfaction Problems

Award details

The constraint satisfaction problem (CSP) is, informally, the computational problem of finding an assignment from a set of values to a set of variables that satisfies a series of given constraints on the values that the variables can take. The CSP is a general enough framework to express a wide range of computational problems, yet it maintains a rich mathematical structure so that to approach it techniques can be drawn from fields as diverse as algebra, logic, graph theory, and combinatorics just to name a few. The computational complexity of the CSP and its variants is a very active area of research, with many long-standing open questions and new research directions recently emerging.

Approximation is a particularly fruitful area of interest, which focuses on finding ways to efficiently compute sub-optimal solutions to an instance of the CSP, under the assumption that computing an exact solution is computationally hard. This can take many different forms, such as finding solutions that maximise the number of satisfied constraints (known as max-CSP) or finding solutions that satisfy all the constraints in a qualitatively weaker sense (known as Promise CSPs). One possible topic of emphasis of the PhD project is to focus on the combination of these two approaches. However, the student will have the freedom to pose and explore their own research questions within the broad field of constraint satisfaction theory.

The successful candidate will join a dynamic community of researchers and will have the opportunity to present their research at national and international conferences.

PhD students in the department are encouraged to undertake paid TA work alongside their doctoral studies.

Award value

Stipend: £23,805.00 per annum

Bench Fees: £1,000.00 per annum

Tuition fees: covered in full for home/overseas students

Eligibility criteria

Award open to UK and overseas students.

The successful candidate will have a strong background in theoretical computer science and/or discrete mathematics. Applicants will normally hold, or be about to complete, a Master’s degree in Computer Science, Mathematics, or a closely related field.

Applicants who do not meet these criteria may be able to demonstrate their competence through alternative evidence of achievement or experience.

Application process

Applicants are encouraged to contact Dr Silvia Butti (silvia.butti@kcl.ac.uk) before formally submitting their application, including a summary of their academic background, research interests, and any relevant previous experience.

To be considered for the position candidates must apply via King’s Apply online application system. Details are available on the Department of Informatics website. 

Please apply for Computer Science Research MPhil/PhD (Full-time) and indicate Dr Silvia Butti as the supervisor and quote the project title in your application and all correspondence.

Please ensure to add the code 833 in the Funding section of the application form. Please select option 5 ‘I am applying for a funding award or scholarship administered by King’s College London’ and type the code into the ‘Award Scheme Code or Name’ box. Please copy and paste the code exactly.

The selection process will involve a pre-selection on documents and, if selected, will be followed by an invitation to an interview. If successful at the interview, an offer will be provided in due course.

Contact Details

Dr Silvia Butti (silvia.butti@kcl.ac.uk)

If you require support with the application process please contact informatics-pgr@kcl.ac.uk.