A fully funded 3 year PhD studentship is available at the School of
Informatics, University of Edinburgh, on the topic of "Design and Analysis
of Satisfiability Algorithms". The studentship is funded by the ERC
Consolidator Grant ALUnif: "Algorithms and Lower Bounds: A Unified
Approach", and will be supervised by Rahul Santhanam.
The goal of the project is to design and analyze better algorithms for
Satisfiability and other NP-complete algorithms, guided by
complexity-theoretic ideas. The project belongs to the field of exact
algorithms for NP-hard problems, where we are interested in finding
algorithms for NP-hard problems with worst-case complexity O(2^{cn}),
where c < 1 is as small as possible. Here "n" is the witness size of the
instance. Recently discovered connections between complexity lower bound
techniques and algorithmic analysis suggest new approaches to finding
better exact algorithms, and the student will work with the supervisor in
exploring these new approaches.
The student will join the Algorithms and Complexity Group at the
Laboratory for Foundations of Computer Science (LFCS) in the School of
Informatics. The School of Informatics at Edinburgh is the UK's largest
and strongest research centre for computing and informatics. In the latest
UK Research Assessment Exercise in 2008, Informatics at Edinburgh was
adjudged to deliver more world-leading research than any other university
in the UK. Two winners of the ACM Turing award, which is the highest
distinction in computer science, have taught at Edinburgh.
Applicants should have a strong mathematical background, with an
undergraduate degree in Computer Science, Mathematics or a related area.
Prior experience with the theory of algorithms and/or
complexity theory is highly recommended.
The position is available to UK/EU applicants, but exceptional
international applicants may also be considered. The deadline is March
31. Informal queries may be addressed to Rahul Santhanam
(rsanthan@inf.ed.ac.uk).
To apply, click on the apply button at this link:
http://www.jobs.ac.uk/job/AIF821/phd-studentship/
---------------
Rahul Santhanam
--
The University of Edinburgh is a charitable body, registered in
Scotland, with registration number SC005336.
**********************************************************
*
* Contributions to be spread via DMANET are submitted to
*
* DMANET@zpr.uni-koeln.de
*
* Replies to a message carried on DMANET should NOT be
* addressed to DMANET but to the original sender. The
* original sender, however, is invited to prepare an
* update of the replies received and to communicate it
* via DMANET.
*
* DISCRETE MATHEMATICS AND ALGORITHMS NETWORK (DMANET)
* http://www.zaik.uni-koeln.de/AFS/publications/dmanet/
*
**********************************************************