Ph.D Student in Theoretical Computer Science
Please note that the job is no longer active!
KTH CSC announces a PhD position in Theoretical Computer Science in the area of proof complexity...
For more information about CSC, go to www.kth.se/csc.
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.
Nr of positions available : 1
Please note that the full description may be available in the national language since some job boards have their own publication policy. Thank you for your understanding!
Early stage researcher or 0-4 yrs (Post graduate)
To better plan and organise their stay in a foreign European country, researchers and their families can also benefit of the free and personalised assistance offered by the EURAXESS Services Centres, a network of more than 200 centres located in 40 different European countries.
KTH Royal Institute of Technology
Publish your job vacancies & fellowship programmes or Post your CV