学界|圣安德鲁斯大学招募优化算法博士

Multidimensional words form a novel class of combinatorial structures, representing structures in two or more dimensions such as QR codes, pictures, sudokus, and crystal structures. While these objects are studied under numerous names, these all ultimately correspond to the same underlying structure, namely a multidimensional array where each entry is some type of symbol, for example black or white squares for a QR code, letters in a crossword, or pixels in a picture. Despite the widespread applicability of these objects, there has been very little research on the algorithmic and combinatorial properties of these objects.

This project will look to address this by undertaking an in-depth look at several novel classes of multidimensional words, providing opportunities to study both combinatorial and algorithmic problems on these words. With each application of these objects having many unique questions, there are many possible research directions available, spanning numerous areas of Theoretical Computer Science. Further, as a relatively new field, there are many opportunities to establish foundational results for these objects.

Potential Directions：

This project offers a large number of possible directions for the student to study. Some, but by no means all, possibilities are listed below.

*  Investigating the de Bruijn torus, a fundamental object in combinatorics with many unanswered questions regarding their existence and construction.

*  Extending the notions of Parikh Vectors to multidimensional space, and developing new algorithms for enumerating words under these constraints. These constraints can be thought of as a generalisation of the rules in sudokus, restricting the number of types each symbols (numbers in the case of sudokus) in each row and column.

*  Counting and enumerating equivalence classes of multidimensional words under group operations. This represents challenges such as designing codes that need to be uniquely identifiable from any rotation, or identifying pictures that have been altered though simple operations like reflection

*  Implementing solutions using constraint programming to answer NP-Hard problems on multidimensional words, such as subsequence detection or sudoko solving.

Some initial guidance will be given for determining the research questions studied, however during the course of the PhD the successful applicant will be given a great deal of freedom in deciding which direction to study. Depending on the direction the student wishes to go, there will also be opportunities for collaboration with external collaborators, both at the national and international level.

Informal inquiries may be directed to Dr Duncan Adamson( duncan.adamson@st-andrews.ac.uk )

The successful applicant will be fully funded, covering tuition and a stipend of £19,795 (or the standard UKRI stipend, if it is higher) for a period of 3.5 years. This funding is available regardless of country of origin.