Candidates should have a strong background in either theoretical computer science and mathematics, or a keen interest in the construction and analysis of algorithms. However, we encourage inquiries from students with other backgrounds, too, since there are many different topics to tackle in the proposed PhD project. Candidate aptitude may be demonstrated through excellent grades in relevant courses, publications in reputable conferences or journals, or recognition in programming or mathematics competitions. PhD students at TCSLAB have four-year full-time employed positions, but they typically include 20% teaching (and the position is prolonged for one year). The positions are fully funded (including travel money) and come with a competitive salary.
TCSLAB does fundamental research on algorithms, computational complexity, and algebraic approaches, with a particular focus on constraint satisfaction problems and related problems which are often of interest in artificial intelligence. Our work on the borderline of AI is facilitated by the fact that TCSLAB is part of the Division of Artificial Intelligence and Integrated Computer Systems (AIICS): AIICS mainly works in artificial intelligence, its foundations, and its application to intelligent artifacts and decision support systems. TCSLAB additionally cooperates with a large number of academic institutions around the world and we have several joint research projects that are currently active.
The new project lies in the intersection of complexity theory and universal algebra. Here, the idea is to study the complexity of NP-hard CSPs under a more fine-grained lens than ordinary polynomial-time reductions. For example, if a given CSP is NP-complete, then it is unlikely to be solvable in polynomial time, but how fast can be solved by a superpolynomial algorithm? Is it possible to construct mathematical methods which allow us to say whether a certain algorithmic scheme is applicable? As the ultimate goal, can one characterize all CSPs solvable faster than exhaustive search? A possible way to pursue this goal is by adapting the influential algebraic approach for studying (classical) computational complexity to the fine-grained setting.
The details concerning the projects and the associated positions are currently being finalized but the exact dates when the positions will be officially announced is not yet decided. We strongly encourage those interested in becoming a PhD student within these projects to contact Victor Lagerkvist (victor.lagerkvist@liu.se) for informal inquiries and discussions. Please note that we can only hire for open positions that are advertised in official announcements, and all applications must be made via the official recruitment system.
Information about IDA: www.ida.liu.se
Information about LiU: www.liu.se
The study of the limits of efficient computation is foundational mathematical research, but research results in computational complexity theory have had major impact in many areas of computer science and other scientific disciplines. In particular, it has given rise to some of the most important open problems in modern mathematics: the famous P =? NP question is one example.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************
Posts
