Back to search results

PhD Studentship: Testing the Limits of Efficient Algorithms for Computationally Hard Problems

University of Birmingham - School of Computer Science

Qualification Type: PhD
Location: Birmingham
Funding for: UK Students, EU Students, International Students
Funding amount: £17,668 stipend p.a.
Hours: Full Time
Placed On: 24th March 2023
Closes: 28th April 2023

The analysis of algorithms is a substantial contribution that mathematics has made to computer science. Typically, the efficiency of an algorithm is determined by how much resource the algorithm consumes as a function of its input size. However, most interesting computational problems are NP-hard which means that (unless P=NP) there is no polynomial time algorithm for such problems. The paradigm of parameterized (FPT) algorithms identifies different parameters of the input, and aims to design algorithms whose running time is efficient when these parameters are bounded.

This project aims to obtain optimal algorithmic results for NP-hard graph problems on special graph classes such as planar graphs, bounded genus, minor-free, intersection graphs in Euclidean space, etc. Given the NP-hardness of a problem on general graphs, the question is how exactly does the algorithmic complexity of the problem change according to the topology of special graph classes? Positive algorithmic results can be viewed as an indication to impose this topology on the input graph in practice to ensure that we can run efficient algorithms, whereas lower bounds are an indication that we need to impose stronger topological structure if the goal is to be able to use efficient algorithms.

There are two main (complementary) parts of the project:

  1. Algorithmic results: In this part of the project, the aim is to design efficient algorithms for NP-hard problems on special graph classes by exploiting the topological structure. This will involve designing new algorithmic techniques in addition to learning how to use existing techniques.
  2. Lower Bounds: In this part of the project, the aim is to show conditional (on well-believed hypothesis from computational complexity) lower bounds which match the running time of the algorithms designed in Part 1.

In addition to problems from theoretical computer science, there is also the possibility to undertake this systematic analysis for graph-theoretic problems arising from other areas of computer science such as machine learning, bioinformatics, etc.

You should have an undergraduate degree in Mathematics or Computer Science (with a strong theoretical content). Ideally, your degree includes modules on graph theory, algorithms, discrete mathematics, writing proofs, etc. Programming experience is not necessary but would be helpful. During the PhD project, you will develop skills in algorithmic techniques (bidimensionality, dynamic programming, graph minor theory, etc.) and lower bound methodologies (parameterized reductions, NP-hardness). There will also be opportunities to develop your skills in writing, presentation and teaching.

You will need a First or Upper Second-Class Honours undergraduate degree and/or postgraduate degree with Distinction (or an international equivalent). We also consider applicants from diverse backgrounds that have provided them with equally rich relevant experience and knowledge. Full-time and part-time study modes are available.

We want our PhD student cohorts to reflect our diverse society. UoB is therefore committed to widening the diversity of our PhD student cohorts. UoB studentships are open to all and we particularly welcome applications from under-represented groups, including, but not limited to BAME, disabled and neuro-diverse candidates. We also welcome applications for part-time study.

We will consider applications from students wishing to start their studies in autumn 2023 or during the 2022-23 academic year.

We value your feedback on the quality of our adverts. If you have a comment to make about the overall quality of this advert, or its categorisation then please send us your feedback
Advert information

Type / Role:

Subject Area(s):

Location(s):

PhD tools
 

PhD Alert Created

Job Alert Created

Your PhD alert has been successfully created for this search.

Your job alert has been successfully created for this search.

Ok Ok

PhD Alert Created

Job Alert Created

Your PhD alert has been successfully created for this search.

Your job alert has been successfully created for this search.

Manage your job alerts Manage your job alerts

Account Verification Missing

In order to create multiple job alerts, you must first verify your email address to complete your account creation

Request verification email Request verification email

jobs.ac.uk Account Required

In order to create multiple alerts, you must create a jobs.ac.uk jobseeker account

Create Account Create Account

Alert Creation Failed

Unfortunately, your account is currently blocked. Please login to unblock your account.

Email Address Blocked

We received a delivery failure message when attempting to send you an email and therefore your email address has been blocked. You will not receive job alerts until your email address is unblocked. To do so, please choose from one of the two options below.

Max Alerts Reached

A maximum of 5 Job Alerts can be created against your account. Please remove an existing alert in order to create this new Job Alert

Manage your job alerts Manage your job alerts

Creation Failed

Unfortunately, your alert was not created at this time. Please try again.

Ok Ok

Create PhD Alert

Create Job Alert

When you create this PhD alert we will email you a selection of PhDs matching your criteria.When you create this job alert we will email you a selection of jobs matching your criteria. Our Terms and Conditions and Privacy Policy apply to this service. Any personal data you provide in setting up this alert is processed in accordance with our Privacy Notice

Create PhD Alert

Create Job Alert

When you create this PhD alert we will email you a selection of PhDs matching your criteria.When you create this job alert we will email you a selection of jobs matching your criteria. Our Terms and Conditions and Privacy Policy apply to this service. Any personal data you provide in setting up this alert is processed in accordance with our Privacy Notice

 
 
 
More PhDs from University of Birmingham

Show all PhDs for this organisation …

More PhDs like this
Join in and follow us

Browser Upgrade Recommended

jobs.ac.uk has been optimised for the latest browsers.

For the best user experience, we recommend viewing jobs.ac.uk on one of the following:

Google Chrome Firefox Microsoft Edge