PhD Studentship in Algorithms and Complexity

Full tuition-fee waiver and stipend of approximately $25,000 per annum (GBP 17,000)

Department of Computer Science, Royal Holloway University of London

Tentative starting date: September/October of the year

The Department of Computer Science at Royal Holloway University of London is offering a three-year full-time PhD studentship in algorithms and complexity. The studentship includes a full tuition-fee waiver and a maintenance award in line with the level recommended by Research Councils UK (exact value to be confirmed, circa GBP 16,000 pa). The student will be hosted in the Center for Algorithms and Applications and will work under the supervision of Dr Iddo Tzameret.

This is a competitive-based PhD position, meaning that the candidate will compete against other PhD candidates of the department of computer science. I expect, though, that strong candidates would be able to get an offer (as there are several such PhD positions offered).

The project is broadly in the area of computational complexity with an emphasis on satisfiability and the complexity of proofs. The successful candidate will investigate fundamental aspects of the Boolean satisfiability problem SAT from possibly different aspects - combinatorial, algebraic and logical - with a possibility to engage as well in applied or empirical study of SAT-solving and other applications related to SAT, depending on the preferences and qualifications of the candidate.

Applications should be made through the online application system at Royal Holloway, University of London HERE.

Requirements: The candidate should be an EU/UK resident. The successful candidate will have obtained a first-class Bachelors or Masters degree in Computer Science, Mathematics or a cognate discipline, have a solid understanding of foundational aspects of computer science and, specifically, computational complexity (knowledge of logic will also be appreciated), and be highly motivated. Every application will be analysed individually.

For any inquiries about the position, please contact me (Iddo Tzameret) at

The Computer Science Department at Royal Holloway, University of London, is one of the UK's leading centers for research into Computer Science. In the most recent Reference Excellent Framework (REF 2014), the department ranked 11th in the UK for the quality of research output, with over 32% of publications recognized as world leading, and 55% internationally excellent. The department consists of world-leading researchers in algorithms and complexity, bioinformatics, distributed and global computing, machine learning, software language engineering, and applications of logic in computer science. Research students enjoy a very lively research culture and are fully involved in the research activities of the Department (and share their successes). The Department also funds students to present their work at international conferences.

*Tentative* description of the project:

While the Boolean satisfiability problem SAT and its variants are at the heart of both theory and practice of computation, the questions surrounding efficient algorithms for SAT pose a great scientific challenge to this day, with no clear vision on how to overcome it. The notable example is the P vs. NP problem that asks whether there is an efficient algorithm for deciding if a Boolean formula is satisfiable.

Nevertheless, great progress has been made in understanding the complexity of specific and restricted versions of SAT and its relatives. For example, it is known that certain families of backtracking algorithms cannot solve SAT efficiently in the worst case; While on the other hand, in some important cases we can achieve efficient algorithms of a specific kind in the average-case; From yet another perspective, when dealing with inputs coming from the industry, current industrial level SAT-solvers are able to quickly solve instances incorporating millions of variables.

The project foremost aim is to advance the frontiers of our understanding of the satisfiability problem and its complexity, taking into account established approaches, and specifically the one coming from Proof Complexity. The area of proof complexity investigates the possibility and limitations of efficient non-deterministic algorithms (in other words, proofs) for the un-satisfiability problem, and the project will study and utilise recent advances in this field; focusing on the fundamental questions of complexity lower bounds, recently developed approaches for achieving strong lower bounds, as well as on efficient algorithms for specific cases.