Fully Funded EPSRC and Swansea University PhD Scholarship: Reconstruction of Mixed-Up Messages

Funding providers: EPSRC and Swansea University's Faculty of Science and Engineering

Subject areas: Mathematics, Probability, Information theory, Efficient Algorithms

Project description: 

A famous problem in probability, information theory and theoretical computer science is the following: A long message over a finite alphabet is sent via an information channel. Now suppose that the message that arrives at the receiver is not the original one, but a randomly corrupted version. Suppose further that the receiver knows the random mechanism corrupting the message. Now the question is: Can the receiver recover the original message?

To formulate this mathematically, suppose that to each integer number a letter from the finite alphabet is assigned and a simple random walk runs on the integers. At each time t it registers the letter it observes at its current position. This produces a new random sequence of letters. Now the question is: Can the original message be reconstructed with probability one from this newly created random sequence? In general, it cannot, but under appropriate restrictions, it can. Lindenstrauss (1999) showed that there are messages which cannot be reconstructed. However, it is known that almost surely a “typical” message, drawn at random according to a given distribution, can be reconstructed (possibly up to shift and/or reflection)

A natural extension of this problem is to consider it in higher dimensions. In the proposed project we want focus dimension two, which is a critical case, and understand under which conditions a finite piece of the message can be reconstructed in polynomial time (polynomial in relation to the size of the piece reconstructed). In addition, we aim to provide a concrete algorithm that achieves this reconstruction without using supercomputers and quantum computers.

Eligibility

Candidates must hold an Upper Second Class (2.1) honours degree or an appropriate master’s degree with a minimum overall grade at ‘Merit’ in a closely related discipline. If you are eligible to apply for the scholarship (i.e. a student who is eligible to pay the UK rate of tuition fees) but do not hold a UK degree, you can check our comparison entry requirements. Please note that you may need to provide evidence of your English Language proficiency.

English Language: IELTS 6.0 Overall (with no individual component below 5.5) or Swansea University recognised equivalent.

The candidate is expected to have a strong mathematical background. Computational and programming skills in one or more programming languages such as Python or Matlab are preferred. Strong interpersonal skills and the capacity to work and learn independently will be required.

This scholarship is open to candidates of any nationality.

Please visit our website for more information on eligibility.

Funding

This scholarship covers the full cost of tuition fees and an annual stipend at UKRI rate (currently £18,622 for 2023/24).

Additional research expenses will also be available. 

Advert information