Topics in Randomised Algorithms and Computational Complexity
Andreas Galanis is willing to supervise projects in the areas of randomised algorithms and computational complexity. Problems
of interest include (i) the analysis of average case instances of hard combinatorial problems (example: can we satisfy a random
Boolean formula?), and (ii) the computational complexity of counting problems (example: can we count approximately the number
of proper colourings of a graph G?). The projects would suit mathematically oriented students, especially those with an interest
in applying probabilistic methods to computer science.