Jakob Nordström / Open positions / PhD positions in theoretical computer science and combinatorial optimization

PhD Positions in Theoretical Computer Science and Combinatorial Optimization

The Department of Computer Science at Lund University invites applications for one PhD position in theoretical computer science and one PhD position in combinatorial optimization.

Job Description

The PhD students will be working in the Mathematical Insights into Algorithms for Optimization (MIAO) group headed by Jakob Nordström, which is active at both Lund University and the University of Copenhagen on either side of the Öresund Bridge.

The MIAO research group has a unique profile in that we are doing cutting-edge research both on the mathematical foundations of efficient computation and on state-of-the-art practical algorithms for real-world problems. This creates a very special environment, where we do not only conduct in-depth research on different theoretical and applied topics, but where different lines of research cross-fertilise each other and unexpected and exciting synergies often arise. Much of the activities of the group revolve around powerful algorithmic paradigms such as, e.g., Boolean satisfiability (SAT) solving, Gröbner basis computations, integer linear programming, and constraint programming. This leads to classical questions in computational complexity theory—though often with new, fascinating twists—but also involves work on devising clever algorithms that can exploit the power of such paradigms in practice.

We currently have one opening for a theoretically oriented PhD student, funded by a Consolidator Grant from the Swedish Research Council, and one more applied opening financed by the Wallenberg AI, Autonomous Systems and Software Program (WASP). There is a lot of flexibility as to what kind of research the PhD students will pursue, though, and all candidates are welcome, both those who want to go deep into either theory or practice and those who are inspired by the challenge of bridging the gap between the two.

On the theory side, most of our work is in proof complexity, which studies formal systems for reasoning about logic formulas and other types of problems. Proof complexity has connections to foundational questions in computational complexity theory, but also plays an important role in algorithm analysis by providing a rigorous understanding of the power and limitations of different algorithmic approaches. As often happens in theoretical computer science, our research has revealed deep, and often quite surprising, connections to other areas such as, e.g., circuit complexity, communication complexity, and hardness of approximation, and so the research activities might well involve also such areas.

On the practical side, we want to gain a more rigorous scientific understanding, and improve the performance, of modern algorithms for automated reasoning and combinatorial optimization. We are particularly interested in designing algorithms that can exploit sophisticated mathematical techniques to achieve exponential improvements in performance compared to the current state of the art—something that theoretical research suggests should be possible, but that has so far been hard to achieve in practice.

Quite recently, we have also made some breakthrough research on how to verify the correctness of state-of-the-art algorithms for combinatorial optimization. Such algorithms are often highly complex, and even mature commercial solvers are known to sometimes produce wrong results. Our goal is to design a new generation of certifying combinatorial solvers with so-called proof logging, meaning that the solvers output not only a solution but also a machine-verifiable proof that is easy to check and provides 100% formal guarantees that the claimed solution is correct and complete.

These are four-year full-time employed positions, but PhD positions usually (though not necessarily) include 20% teaching, in which case they are prolonged for one more year. The starting date is negotiable but should ideally be as early as possible during the autumn of 2021. All positions in the research group are fully funded, employed positions (including travel money) that come with an internationally competitive salary.

Qualifications

To be eligible to apply for this position, applicants need to have or be close to obtaining either an MSc degree or a 4-year BSc degree. A suitable background is, for instance, a degree in computer science, mathematics, electrical engineering, or possibly technical physics with a theoretical specialization.

The successful candidate is expected to have a strong background and passionate interest in computer science and mathematics. Problem solving skills and creativity are a must. For candidates aiming to do more applied research excellent programming skills are also crucial.

The working language of the group is English, and knowledge of English is also fully sufficient to navigate every-day life in Scandinavia in general. It might also be worth mentioning that Scandinavian countries routinely score at the absolute top in rankings of quality of life such as, e.g., the OECD Better Life Index.

Workplace

Lund University was founded in 1666 and is repeatedly ranked among the top 100 universities in the world. Lund Technical College (LTH) forms the Faculty of Engineering at Lund University, where research of the highest international standard is conducted.

The Department of Computer Science at LTH is a partner in the Wallenberg AI, Autonomous Systems and Software Program (WASP), which is Sweden's largest ever individual research program and addresses research on artificial intelligence broadly construed, and also in the ELLIIT Excellence Centre focused on basic and applied research in information technologies. Furthermore, there are extensive collaborations with the University of Copenhagen, the IT University of Copenhagen (ITU), and the Technical University of Denmark (DTU) on the other side of the Öresund Bridge.

Application

The application deadline is September 13, 2021 at midnight local time. Early applications are welcome, since this will help speed up the recruitment process, but all applications submitted before the deadline will be given equal consideration.

Applications must be submitted via the Lund University recruitment system. Please see the official advertisement at lu.varbi.com/en/what:job/jobID:420266 for more details including a link to the application form.

The application should include the following documents:

  1. Curriculum vitae.
  2. University grade transcripts.
  3. Brief statement as to why the applicant wishes to conduct doctoral studies, including a description of the applicant's qualifications and interests.
  4. Diploma and transcripts of records (BSc and MSc).
  5. If applicable, copies of the applicant's MSc thesis (or possibly BSc thesis) and any research publications.
  6. Names and addresses for three references who might be contacted for reference letters later in the recruitment process.
Please observe that all the documents above should be in English (or for official documents possibly in Swedish).

Lund University welcomes applicants with diverse backgrounds and experiences. We regard gender equality and diversity as a strength and an asset.

Further Information and Contact Details

Further information about the Department of Computer Science can be found at cs.lth.se/english/.

Inquiries about the position can be made to Jakob Nordström at jakob.nordstrom@cs.lth.se.

Published by: Jakob Nordström <jn~at-sign~di~dot~ku~dot~dk>
Updated 2021-07-27