PhD Position in Theoretical Computer Science
The Theoretical Computer Science group at KTH Computer Science and Communication (KTH CSC) invites applications for a PhD position in Theoretical Computer Science (Algorithms & Complexity).
We are seeking a PhD student in Theoretical Computer Science for the research project “Trading Time for Approximation in Optimization” in the areas of approximation algorithms and exact algorithms.
Many important computational problems that appear in practice are NP-hard, meaning that it is unlikely that they can be solved in polynomial time.
An approach to dealing with NP-hard problems that has flourished in the last few decades is the study of how good approximate solutions can be found efficiently. For many fundamental problems such as Max 3-Sat, Max Clique, and Max Cut, we now know precisely the best possible approximation quality achievable by polynomial time algorithms.
A different approach is to design faster exact algorithms for these problems. While it is likely that such algorithms require exponential time, the precise exponential behaviour has a strong influence on how large problem instances can be solved. In recent years there have been improved algorithms for many fundamental problems such as 3-Sat, Graph Coloring, and Hamiltonicity.
These two approaches are in some sense two extremes of how one can cope with NP-hard problems. For many problems, the best approximation algorithm, while fast, give solutions that are not good enough, whereas the best exact algorithm is too slow to solve instances of interest. The goal of this project – and your mission, should you choose to accept it – is to investigate what trade-offs are possible between these two extremes.
The project is led by Per Austrin and is financed by a Project Research Grant from the Swedish Research Council.
This is a four-year time-limited position, but normally includes 20% departmental duties, usually teaching, in which case it can be prolonged for one more year. Doctoral students must be registered at KTH. The starting date is open for discussion, though ideally we would like the successful candidate to start at the end of Summer 2013.
Form of employment: Time-limited
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., algorithms and complexity theory or similar areas) and Mathematics (preferably combinatorics and discrete analysis). Exceptional candidates are always of interest regardless of formal prerequisites. Problem solving skills and creativity are a must. Practical programming skills are a plus.
The working language of the TCS group is English, and knowledge of English is also fully sufficient to navigate life in Sweden in general.
Applicants must be strongly motivated for doctoral studies, possess the ability to work independently and perform critical analysis as well as possess good levels of cooperative and communicative abilities.
KTH 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.
The School of Computer Science and Communication at KTH (KTH CSC) 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.
The Theoretical Computer Science group at KTH 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.
Application deadline: March 15, 2013
Applications should be sent via email to email@example.com. Write the reference number D-2013-0090 in the email subject. The application and all attachments should be sent as PDF files.
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 web page, or on whatever page linked you here.)
For enquiries about the project please contact:
For enquiries about Ph.D studies and employment conditions please contact: