TCSLAB is currently quickly growing, and we expect several PhD students and postdocs to join the group in the near future. We want to come in contact with prospective PhD students who want to pursue a career within theoretical computer science and with an emphasis on algorithms and computational complexity (see the project descriptions below for contact details). The reason for doing this before the formal announcement is to encourage informal inquiries and discussions without the timing constraints enforced by the application deadline. 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. 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.
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.
TCSLAB will initiate three new projects that are all based on constraint satisfaction problems (CSPs). CSPs are a highly important class of formalisms across many subareas of computer science (for instance, automated reasoning, machine learning, scheduling, computational linguistics, optimisation, computational biology, and verification) and CSPs have been used in computer science since the early 1970s to specify various problems. Many (but not all!) practically interesting CSPs are NP-hard and are thus regarded to be intractable. The Boolean satisfiability problem is a well-known NP-hard example while a polynomial-time example is to solve linear equations over the rationals. Gaining a better understanding of the computational complexity of CSPs is an extremely relevant task, and. the projects outlined below are all concerned with this line of research.
Project 1: Fine-grained complexity of constraint satisfaction problems via 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 leader of this project is Victor Lagerkvist.
Project 2: Faster algorithms and lower bounds for non-monotonic reasoning.
The goal of this project is to construct new and improved algorithms for NP-hard non-monotonic reasoning problems. These problems are related to CSP and satisfiability problems but have different aims and objectives, e.g., to find an actual explanation of a phenomenon that is consistent with the current knowledge base, rather than just checking satisfiability. Thus, are non-monotonic problems intrinsically different from CSP problems, and are new algorithmic techniques necessary to solve them faster? A promising starting point is the propositional abduction problem where a complete complexity dichotomy is known. Can this problem be solved faster than exhaustive search, and can its complexity be related to existing problems believed to be hard?
This is a joint project with Högskolan i Jönköping and it is jointly led by Victor Lagerkvist and Johannes Schmidt.
Project 3: Parameterized complexity of constraint satisfaction problems.
Realistic computational problems often contain "hidden structure" that can be exploited for efficient solving. The prime method for studying hidden structure is parameterized complexity that enables complexity analysis on a finer scale than in the classical setting. The parameterized view on computation has led to a theory that is simultaneously mathematically challenging and practically applicable. The project concerns upper and lower bounds on the parameterized complexity of CSP problems, and with the long-term goal on obtaining general theoretical frameworks for such analysis. In particular, we are interested in novel methods for algorithm construction. The leader of this project is Peter Jonsson.
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) and/or Peter Jonsson (peter.jonsson@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
**********************************************************
*
* 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
