AISB opportunities Bulletin Item
PhD student position in theoretical computer science, Stockholm, SWEDEN
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, with education and research spanning from natural sciences to all branches of engineering including architecture, industrial management and urban planning. 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 regularly 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 seeking a PhD student for the research project "Understanding the Hardness of Theorem Proving" in the area of proof complexity with connections to SAT solving. Proving formulas in propositional logic is a problem of immense importance both theoretically and practically. On the one hand, this computational task is believed to be intractable in general, and deciding whether this is so is one of the famous million dollar Millennium Problems (the P vs. NP problem). On the other hand, today so-called SAT solvers are routinely used to solve large-scale real-world problem instances with millions of variables. 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). This project aims to advance the frontiers of proof complexity, and to leverage this research to shed light on questions related to SAT solving. This could potentially also involve research in related areas such as, for example, circuit complexity, communication complexity, or hardness of approximation. The 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 full-time employed position, normally for five years including 20% teaching, with salary according to KTH PhD student regulations (internationally very competitive). The successful candidate is expected to start at the latest in August 2013, although this is to some extent negotiable. The application deadline is May 5, 2013, but candidates are encouraged to apply right away since applications are reviewed on a continuous basis. See http://www.csc.kth.se/~jakobn/openings/D-2013-0301-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.