This webpage is being kept for archival purposes only. Please see www.jakobnordstrom.se/openings for information about currently open positions.PhD Position in Theoretical Computer ScienceThe Department of Computer Science at Lund University invites applications for a PhD position in theoretical computer science.
Job DescriptionThe PhD student 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 fairly unusual profile in that we are doing cutting-edge research both on the theoretical, mathematical foundations of efficient computation and on state-of-the-art applied algorithms for real-world problems. Much of the activities of the group revolve around powerful algorithmic paradigms such as Boolean satisfiability (SAT) solving, Gröbner basis computations, integer linear programming, constraint programming, and semidefinite programming. This leads to classic questions in computational complexity theory—though often with new, interesting twists—but also involves work on devising new algorithmic approaches that can exploit the power of such paradigms in practice. On the theory side, most of our work is in proof complexity, i.e., the study of formal systems for reasoning about logic formulas and other types of problems from the point of view of computational complexity. Proof complexity has connections to foundational questions in computational complexity theory, but another important motivation is algorithm analysis. All algorithms use some kind of method of reasoning to compute solutions to problems, and proof complexity can be used to analyse the potential and limitations of such methods (and thereby of the algorithms using them). 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, hardness of approximation, and finite model theory, 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 state-of-the-art solvers for combinatorial optimization problems. We are particularly interested in harnessing powerful mathematical tools such as Gröbner bases or 0-1 integer linear programming (also known as pseudo-Boolean solving) to achieve exponential improvements in performance, which seems possible in theory but has so far been hard to achieve in practice. Our most active line of work right now is focusing on combining ideas from pseudo-Boolean solving, MaxSAT solving, mixed integer linear programming (MIP), and constraint programming (CP) to construct new combinatorial solvers that have the potential to go significantly beyond the current state of the art. Another research area of interest is 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. We want to redesign state-of-the-art combinatorial solvers to make them certifying, i.e., so that they output not only a solution but also a simple, machine-verifiable proof that the claimed solution is correct and complete—this is also known as proof logging. Importantly, such machine-verifiable proofs should be very easy to generate and should require low overhead on the solver side, but should at the same time be very easy to check efficiently, and should provide 100% formal guarantees of correctness.
This is a four-year full-time employed position, 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. The position is fully funded and comes with a 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. Applicants need to be be strongly motivated for doctoral studies; should possess the ability to work independently and perform critical analysis, and are also required to have good cooperative and communicative abilities. A good command of English in writing and speaking is needed to be able to participate in international collaborations and to publish and present research results in international conferences and journals. The working language of the group is English, and knowledge of English is also fully sufficient to navigate every-day life 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. WorkplaceLund 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), the largest individual research program in Swedish history, and also in the ELLIIT Excellence Centre focused on basic and applied research in information technologies broadly construed. 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. ApplicationThe application deadline is July 5, 2021 at midnight local time. Applications must be submitted via the Lund University recruitment system. Please see the official advertisement at lu.varbi.com/en/what:job/jobID:392181 for more details including a link to the application form. The application should include the following documents:
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 DetailsFurther 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. |