[DMANET] PhD position in TCS at KTH Royal Institute of Technology

The Theory Group at KTH Royal Institute of Technology invites applications
for a PhD position in theoretical computer science.

KTH Royal Institute of Technology is the leading technical university in
Sweden. The Theory Group at KTH (http://www.csc.kth.se/tcs/) offers a
strong research environment covering a wide range of research topics such
as complexity theory and approximation algorithms, computer and network
security, cryptography, formal methods and natural language processing.
The group has a consistent track record of publishing in the leading
theoretical computer science conferences and journals worldwide, and the
research conducted here has attracted numerous international awards and
grants in recent years. We are now set to expand further, and this
position is just one of several new openings.

Proving formulas in propositional logic is a problem of immense importance
both theoretically and practically. This computational task is widely
believed to be intractable in the worst case, although proving (or
disproving) this is a major open problem in theoretical computer science
and mathematics. (This is one of the famous million dollar Millennium
Problems, known as the P vs. NP problem.) In spite of this, today
so-called SAT solvers are routinely used to solve large-scale real-world
problem instances with millions of variables. The intriguing question of
when SAT solvers perform well or badly, and what properties of the
formulas explain this behaviour, remains quite poorly understood.

Proof complexity studies formal systems for reasoning about logic
formulas. This field has deep connections to fundamental questions in
computational complexity, but another important motivation is the
connection to SAT solving. All SAT solvers use some kind of method or
system in which proofs are searched for, and proof complexity analyses the
potential and limitations of such proof systems (and thereby of the
algorithms using them).

Our research aims to advance the frontiers of proof complexity, and to
leverage this research to shed light on questions related to SAT solving.
We want to understand what makes formulas hard or easy in practice, and to
gain theoretical insights into other crucial but poorly understood issues
in SAT solving. We are also interested in exploring the possibility of
basing SAT solvers on stronger proof systems than are currently being
used. In order to do so, however, a crucial step is to obtain a better
understanding of the corresponding proof systems, and in this context
there are a number of well-known and relatively longstanding open
questions in proof complexity that we want to study and try to resolve.

This research project is led by Jakob Nordstrom
(http://www.csc.kth.se/~jakobn) and is financed by a Breakthrough Research
Grant from the Swedish Research Council and a Starting Independent
Researcher Grant from the European Research Council. The group currently
consists of one postdoctoral researcher and two PhD students (in addition
to the project leader). Travel funding is included, and the group also
receives short-term and long-term visitors on a regular basis.

This is a four-year time-limited position, but PhD positions usually (but
not necessarily) include 20% teaching, in which case they are prolonged
for one more year. The successful candidate is expected to start in
August-September 2014, although this is to some extent negotiable.

The application deadline is December 15, 2013. See
http://www.csc.kth.se/~jakobn/openings/D-2013-0620-Eng.php for the full,
formal announcement with more information and instructions for how to
apply. Informal enquiries about this position are welcome and may be sent
to Jakob Nordstrom.


**********************************************************
*
* 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/
*
**********************************************************