På svenska
The positions below have been filled, and this webpage is kept for archival purposes only.
PhD Positions in Theoretical Computer ScienceThe Theoretical Computer Science group at KTH Computer Science and Communication (KTH CSC) invites applications for PhD positions in Theoretical Computer Science with a focus on proof complexity and connections to SAT solving.
The WorkplaceKTH Royal Institute of Technology is the largest and oldest technical university in Sweden. No less than one-third of Sweden's technical research and engineering education capacity at university level is provided by KTH. Education and research spans from natural sciences to all branches of engineering and includes architecture, industrial management and urban planning. There are a total of just over 15,000 first and second level students and more than 1,600 doctoral students. KTH has almost 4,300 employees. KTH Computer Science and Communication is one of Sweden's leading research and education institutions in Information Technology, with activities at both KTH and Stockholm University. The activities of the school focus on higher education and research within the traditional core areas of numerical analysis and computer science; from theory building and analysis of mathematical models to algorithm construction, implementation and simulation. Other core areas of growing importance are technology and methods for the support of human communication and computer mediated cooperation. The applied research includes scientific computing, computer science, computer vision, robotics, neuroinformatics and neural networks, human-computer interaction, media technology, and communication through speech and music. For more information, go to www.kth.se/csc and follow the link to our "international website". The Theoretical Computer Science group at KTH CSC (www.csc.kth.se/tcs) offers a strong research environment spanning 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.
AssignmentWe are seeking PhD students in Theoretical Computer Science 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 (while there are also small formulas known with just a couple of hundreds of variables that cause even state-of-the-art SAT solvers to stumble). 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 explicitly or implicitly define a system in which proofs are searched for, and proof complexity can be seen to analyse 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. We want to understand what makes formulas hard or easy in practice by combining theoretical study and practical experiments, and also to gain theoretical insights into other crucial but poorly understood issues in SAT solving. Another intriguing direction is to explore 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 attack and solve. The project is led by Jakob Nordström (www.csc.kth.se/~jakobn) and is financed by a Starting Independent Researcher Grant from the European Research Council. These are four-year time-limited positions, but they normally include 20% departmental duties, usually teaching, in which case they can be prolonged for one more year. Doctoral students must be registered at KTH. The successful candidates are expected to start in August 2012, although this is to some extent negotiable.
Employment
Form of employment: Time-limited
QualificationsA suitable background for these positions is, for instance, a MSc degree in Computer Science, Mathematics or possibly Technical Physics with a theoretical specialization. The successful candidates are expected to have a strong background and passionate interest in Theoretical Computer Science (in, e.g., complexity theory or similar areas) and Mathematics (preferably combinatorics and algebra). Exceptional candidates are always of interest regardless of formal prerequisites. Problem solving skills and creativity are a must. Practical programming skills are a big plus since it is possible that one part of the overall project will be about performing large-scale computer experiments and developing new prototypes for SAT solvers. Applicants must be strongly motivated for doctoral studies; should possess the ability to work independently and perform critical analysis and also have good levels of cooperative and communicative abilities. They must also have a very good command of English in writing and speaking to be able to participate in international collaborations and to publish and present research results in international conferences and journals. The working language of the TCS group is English, and knowledge of English is also fully sufficient to navigate life in Sweden in general.
Application
Application deadline: January 20, 2012 The deadline for applications has passed, but if you are a very strong candidate you are welcome to send in your application anyway. Applications will be reviewed until the positions have been filled. Applications via email are to be sent to susanneb@csc.kth.se. Write the reference number in the email subject. The application and all attachments should be sent as PDF files.
We also accept hard copy applications sent to: The application should include the following documents:
We are currently gathering information to help improve our recruitment process. We would therefore be very grateful if you could include an answer to the following question in your application: Where did you initially come across this job advertisement? (To which the answer is, if you are reading this: on the project leader's webpages, or on whatever page linked to here.)
Contact(s)
For enquiries about Ph.D studies and employment conditions please contact:
For enquiries about the project please contact:
Union representative |
