Mark's Projects

Here are a few examples of dissertations or projects I would be prepared to supervise (subject to numbers). They are broadly suitable or adaptable for the MSc Logic, MSc Pure Mathematics or 30 credit (two-semester) 4th year MMath projects, although they may require prerequisite knowledge not contained in these courses. Some of them may be adaptable as 3rd year or one-semester 4th year projects. If you have your own ideas, I am happy to consider supervising projects on other topics in or near my research areas. Please contact me to discuss things further.

Generic Complexity

Introduction: Traditional computational complexity measures the difficulty of problems in the "worst case", but in practice the "worst case" often arises very infrequently. Indeed many theoretically "intractable" algorithms are in widespread use, because in practice they nearly always run very fast! Generic complexity is one attempt to study this phenomenon. A problem is generically solvable if there is an algorithm which, given a randomly selected instance of the problem, terminates with the correct answer with high probability. The subtlely lies mainly in defining "randomly selected" and "high probability". Generic complexity was introduced by group theorists in order to study the relative difficulty of undecidable problems involving groups. It turns out that even undecidable problems can be generically easy with respect to very natural probability distributions.

The Project: You would give an exposition of the main ideas of generic complexity, and of some of the results about group-theoretic decision problems. You could then explore applications of the idea outside group theory. Which of the textbook undecidable problems are generically decidable with respect to some sensible probability distribution? What are the generic complexities of some well-known NP-complete problems?

Prerequisites: You will need a basic grounding in computational complexity/decidability theory and group theory, as well as some elementary real analysis (convergence of sequences etc). More advanced knowledge of combinatorial group theory (infinite discrete groups described using generators and relations) is not necessary but would be an advantage.

Tropical Mathematics

Introduction: The tropical semiring (also known as the max-plus semiring) is the algebraic structure formed by the real numbers under the operations of addition and maximum. It shares many of the properties of a field, with addition and maximum playing the roles of field multiplication and field addition respectively. It differs from a field in that there are no inverses under the maximum (field addition) operation, but instead one gains idempotency of addition (since max(a,a) = a). This leads to a radically different, but still rich, algebraic and geometric structure, which has applications in numerous areas of pure mathematics, applied mathematics and computer science.

The Project: You will start by giving an exposition of the most important features of linear algebra over the tropical semiring. Depending on your interests, you could either go deeper into this theory, or study some applications of tropical methods in areas such as enumerative algebraic geometry, combinatorial optimisation or phylogenetics.

Prerequisites: Basic linear algebra and abstract algebraic structures (eg. rings and modules). Some convex geometry would be helpful but is not essential. Familiarity with the areas in which tropical mathematics is applied (eg. algebraic geometry, combinatorial optimisation, biomathematics) might open up some extra avenues to explore.