is one of the largest computer science departments in northern Europe.
We are currently looking to appoint postdoctoral fellows. The positions
are for two years (with the possibility of extension up to a total maximum
of three years) and the application deadline is November 7, 2022.
We welcome applications from highly motivated, talented individuals who
want to join our vibrant academic community, conducting research in
various areas of computer science.
In particular, the Theoretical Computer Science Laboratory (TCSLAB)
is looking for postdocs with a strong background in theoretical
computer science and mathematics who want to perform research within
algorithms and complexity theory. Examples of current research
project include the following.
* Fine-grained complexity. Classical complexity theory aims at separating
easy and hard problem by putting them into complexity
classes---polynomial-time solvable problems versus NP-hard problems
is a common delineation. Fine-grained complexity aims to refine this
distinction into a quantitative understanding of the exact time required to
solve problems, i.e. providing upper bounds (i.e. invent faster algorithms)
and lower bounds (i.e. proving the impossibility of algorithms with given
time bounds under reasonable complexity theoretical assumptions). TCSLAB
mainly study the fine-grained complexity of (1) infinite-domain constraint
satisfaction problems (CSP) with immediate AI applications and (2)
finite-domain CSPs and SAT problems defined via algebraic invariants.
* Algebraic methods for CSPs. The algebraic approach is a highly
influential method for analyzing the computational complexity of CSPs,
based on the idea of describing relations via algebraic properties. It is
the main method behind the recent proof of the CSP conjecture: every
finite-domain CSP is either polynomial-time solvable or NP-complete.
This method is mainly useful for studying classical complexity of
computational problems and it has proven difficult to use it for analyzing
fine-grained complexity. We study ways of generalizing it by, for instance,
utilizing partial polymorphisms. Our work include both methods for
constructing algorithms and for proving lower bounds
* Parameterised complexity. Parameterized complexity is a measure of problem
complexity with one or more input parameters besides input size. This theory
is motivated, for example, by the observation that there exists relevant
problems that require exponential runtime when the complexity is measured
in terms of the input size only, but that are computable in f(k)*poly(n) time
where f is some function, n is input size and k is some problem-specific
parameter. Such problems can often be considered tractable despite their
traditional classification as intractable. This theory provides a systematic
framework for a refined analysis of complex computational problems, and it
is one of the main tools for efficiently solving problems that exhibit
"hidden structure". TCSLAB currently focus on the parameterized complexity of
various CSPs, including problems derived from mathematical computation
such as equation solving.
* Randomized and approximation algorithms. It is well-known that algorithms that guarantee to
compute an exact answer within a given time bound may be much slower than
algorithms that works under slightly relaxed conditions. Examples include
randomized algorithms where the time bound may be inexact and
approximation algorithms where the answer may be inexact. TCSLAB research has
focused on optimisation problems that appear in automated planning,
multi-agent systems, and CSPs. In particular, we are interested in
connections between inexact methods and parameterised complexity.
For questions concerning research at TCSLAB, please contact
professor Peter Jonsson (peter.jonsson@liu.se). For more general questions,
contact the Head of Department Henrik Eriksson (henrik.eriksson@liu.se).
More information about the department, the positions, and the application
procedure can be found here:
https://liu.se/en/work-at-liu/vacancies?rmpage=job&rmjob=20079&rmlang=UK
**********************************************************
*
* 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
