Monday, March 2, 2015

[DMANET] Fully-funded PhD studentship in Algorithms and Complexity at University of Edinburgh

A fully funded 3.5 year PhD studentship is available at the School of
Informatics, University of Edinburgh, on the topic of "Exact Algorithms
for NP-hard Problems". 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 problems, 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 Excellence Framework in 2014, Informatics at Edinburgh was
adjudged to deliver more world-leading research than any other university
in the UK.

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, 2015. Informal queries may be addressed to Rahul Santhanam

To apply, follow the instructions on this web-page:

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
* 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.