Algorithms for Large Graphs - The Design and Analysis of Graph Algorithms in Modern Computational Models

The Department of Computer Science at the University of Sheffield is offering a fully funded 3 year PhD studentship on Algorithms for Large Graphs

Project Description

Graphs or networks are a natural way to describe structural information. For example, users of Facebook and the acquaintance relations among them form a social network, the proteins together with interactions between them define a biological network, and web-pages and hyperlinks give rise to a huge web graph. Due to the rapid development of information technology, many such graphs become extremely large, and are constantly changing, which poses great challenges for efficiently analysing their structures. This project aims to tackle these challenges through the design and analysis of graph algorithms in the modern computational models, including sublinear algorithms (e.g., property testing, streaming algorithms) that read or store only a small portion of the large input while still have provable performance guarantees, and dynamic algorithms that update efficiently the solution of a problem after dynamic changes over the graph. Practical applications of these theoretical studies will also be considered.
This project will be supervised by Dr Pan Peng.
Prospective candidates must have (or expect to have) at least a good honours degree (2.1 or above) or a Master´s degree in Computer Science or Mathematics. The studentship requires good background knowledge in Theoretical Computer Science, discrete mathematics related to computer science and algorithm design.

Funding Notes

This fully funded studentship provides a tax-free living allowance at the standard Research Council rate (£14,777 p.a. for 2018/19) and full UK/EU student tuition fees for three years.

The PhD project commences either in February 2019 or September 2019

We are also accepting applications from self-funded students and we particularly welcome applicants through the China Scholarship Council Scheme.

For informal enquiries please contact Dr. Pan Peng at [Email Address Removed].