Bursa » Theoretical Computer Science, SUEDI

The Workplace

KTH in Stockholm 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 14,000 first and second level students and more than 1,700 doctoral students. KTH has almost 4,600 employees

KTH CSC is one of the most outstanding research and teaching environments in Information Technology in Sweden with activities at KTH and partly at Stockholm University. We conduct education and research in both theoretical and applied computer science. Theoretical computer science ranges from theory building and analysis of mathematical models to algorithm construction, implementation and simulation. Applied computer science covers a wide spectrum from computer vision, robotics, machine learning, high performance computing, visualization, computational biology, neuroinformatics and neural networks, and speech and music communication. We also conduct applied research and training in media technology, human-computer interaction, interaction design and sustainable development.

For more information about CSC, go to www.kth.se/csc.

Assignment

KTH CSC announces a PhD position in Theoretical Computer Science 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. 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 one of the major open problems 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.

The project is led by Jakob Nordström  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 two PhD students and a postdoctoral researcher (in addition to the PI).

This is a four-year time-limited position that can be extended up to a year with the inclusion of a maximum of 20% departmental duties, usually teaching. In order to be employed, you must first apply and be accepted as an doctoral student at KTH. The successful candidate is expected to start at the latest in August 2014, although this is to some extent negotiable.

Employment

Form of employment: Time-limited
Work time: Full time
The salary follows the regulations provided by KTH
Start date: By agreement
Number of positions: 1

Qualifications

To be eligible to apply for this position, applicants need to have or be close to obtaining either an MSc degree or a 4-year BSc degree. A suitable background for this position is, for instance, a 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). Problem solving skills and creativity are a must. Practical programming skills are a plus.

Applicants must be strongly motivated for doctoral studies, possess the ability to work independently and perform critical analysis and also possess 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: December 1, 2013
Employer's reference: D-2013-0620

Applications should be emailed to: Camilla Johansson, e-mail: applications9@csc.kth.se. If you have any questions, contact us at: jobs@csc.kth.se. Write the reference number in the email subject. (CV, etc. should be sent in separate attachments, as PDF-files, not in a compressed archive)

We also accept hard copy applications sent to:

KTH, CSC
Att.: Camilla Johansson,
Lindstedtsvägen 3, plan 4,
SE-100 44 Stockholm, Sweden

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 thesis (or possibly BSc thesis) 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 within your application: Where did you initially come across this job advertisement?