Sweden: PhD Student in Theoretical Computer Science

Deadline: 14 Jan. 2013

KTH School of Computer Science and Communication (CSC) announces a PhD position in Theoretical Computer Science with a focus on proof complexity and connections to SAT solving.

Assignment

KTH Computer Sicence and Communication (CSC) is looking for a PhD student  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.

The Theoretical Computer Science group ( www.csc.kth.se/tcs) at CSC 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.

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 even 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).

 

Employment

Form of employment: Time-limited
Work time: Full time
Salary: According to KTH regulations for PhD students
Start date: By agreement
Number of positions: 1

Qualifications

A suitable background for this position is, for instance, a MSc degree in Computer Science, Mathematics or possibly Technical Physics with a theoretical specialization. The successful candidate is 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, possess the ability to work independently and perform critical analysis as well as possessing 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 14, 2013
Employer's reference: D-2012-0439

Applications should be sent via email to Kerstin Lagerstedt at jobs@csc.kth.se. Write the reference number in the subject line. The application and all attachments should be sent as PDF files.

The application should include the following documents:

1. Curriculum Vitae.
2. University grade transcripts.
3. Brief statement as to why the applicant wishes to conduct doctoral studies, including a description of the applicant’s qualifications and interests.
4. If applicable, copies of the applicant’s MSc project report and any research publications.
5. Name and address of three referees.

Please observe that all the documents above should be in English (or for official documents possibly in Swedish).

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?

Contact(s)

For enquiries about Ph.D studies and employment conditions please contact:
Eva-Lena Åkerman, HR Manager
Phone: +46 8 790 91 06
Email: ela@csc.kth.se

For enquiries about the project please contact:
Jakob Nordström, Assistant Professor
Phone: +46 8 790 69 19
Email: jakobn@kth.se