Below are some possible topics. Many of the topics are quite classical, indeed a large part of this list consists of winners of the Gödel Prize. For each topic, one paper has been mentioned to give you an idea of what to topic is about, and a starting point for finding literature. However it is not intended that you should base your work on just that one paper.

Quantum computing

The idea of quantum computing is to utilise the inherent parallelism in quantum mechanical systems, where the components of the wave function evolve independently of each other. Quantum computers would not change the limit of what is computable, but might make some problems much faster to solve.

Peter W. Shor (1997). Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Journal on Computing 26(5):1484–1509.

Interactive proof systems (Lilu Xu)

Interactive proof systems are a way of analysing computational complexity by studying games between two players. This is related to topics such as zero-knowledge proofs and the PCP theorem.

László Babai and Shlomo Moran (1988). Arthur-Merlin games: a randomized proof system, and a hierarchy of complexity classes. Journal of Computer and System Sciences 36(2):254–276.

Shafi Goldwasser, Silvio Micali and Charlie Rackoff (1989). The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1):186–208.

Rendezvous in graphs

Consider two agents that move in a graph, hoping to end up in the same node. What can they do, assuming they do not initially know the topology of the graph?

Anders Dessmark, Pierre Fraigniaud, Dariusz R. Kowalski and Andrzej Pelc (2006). Deterministic Rendezvous in Graphs. Algorithmica 46(1):69–96.

Online algorithms and competitive analysis

There are many optimisation problems where it might be natural that the all the input is not available at once, but decisions must be made sequentially as new input becomes available. For example, in scheduling we may need to get jobs started before we know what jobs are coming next. In competitive analysis, one compares the quality of optimisation result in such a scenario to what could have been achieved if all the input was available beforehand.

Baruch Awerbuch, Shay Kutten and David Peleg (1992). Competitive distributed job scheduling. In Proc. 24th Annual ACM Symposium on Theory of Computing (STOC '92), pp. 571–580.

Streaming algorithms

In data mining applications, the amount of data is typically huge, and often more data is generated continuously. In such situations, it is not feasible to try to first store all the data and then apply some batch algorithms. Instead, whatever computations we wish to do, must be made immediately as the data arrives, keeping in memory only the minimum amount of bookkeeping information.

Noga Alon, Yossi Matias, Mario Szegedy (1999). The space complexity of approximating the frequency moments. Journal of Computer and System Sciences 58(1):137–147.

Spectral clustering (Amin Alizadeh)

Spectral clustering uses linear algebra to analyse the whole matrix of pairwise similarities between the data points.

Ulrike von Luxburg (2007). A tutorial on spectral clustering. Statistics and Computing 17(4):395–416.

Multi-armed bandits

Imagine you have a fixed amount of coins you have to use to play on a row of slot machines (``one-armed bandits''). The machines have different winning probabilities, but you don't initially know them. How do you balance between exploitation (playing machines that have given good wins up to now) and exploration (trying out different machines to know which ones are good)? Traditionally this has been analysed statistically, but more recently also the game-theoretic on-line learning framework has been applied.

Peter Auer, Nicolò Cesa-Bianchi, Yoav Freund and Robert E. Schapire (2003). The nonstochastic multiarmed bandit problem. SIAM Journal on Computing 32(1):48–77.

Boosting (Beenish Qaiser)

Boosting is a machine learning method where the basic idea is to take a large number of hypotheses that might not individually be very good and combine them into a much better aggregated hypothesis.

Yoav Freund and Robert E. Schapire (1997). A decision-theoretic generalization of on-line learning and an application to boosting. Journal of Computer and System Sciences 55(1):119–139.

Random projections (Samuli Sillanpää)

Random projections are a technique used in dimension reduction, where the aim is to transform data points from a high dimensional space into a (possibly much) lower dimensional subspace, such that the data is altered as little as possible. If this kind of transformation can be done while still preserving the essential characteristics of the data, the data can be thought as residing inside a lower dimensional subspace, that's embedded inside the higher dimensional data space. Dimension reduction helps to make the data more easily learnable: Applying the learning algorithm (classification, clustering etc.) to the transformed data helps in avoiding the curse of dimensionality. At the same time, the computational requirements are decreased, which might be needed for further processing to be feasible.

Samuel Kaski (1998). Dimensionality reduction by random mapping: fast similarity computation for clustering. Proc. 1998 IEEE International Joint Conference On Neural Networks, volume 1, pages 413–418.

Wavelet trees (Pekka Mikkola)

Paolo Ferragina, Raffaele Giancarlo and Giovanni Manzini (2009). The myriad virtues of Wavelet Trees. Information and Computation 207(8):849–866.

Collision detection (Mikko Sysikaski)

Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha and Madhav Ponamgi (1995). I-COLLIDE: an interactive and exact collision detection system for large-scale environments. Proc. 1995 Symposium on Interactive 3D Graphics, pages 189–218.

Gino van den Bergen (1998). Efficient collision detection of complex deformable models using AABB trees. Journal of Graphics Tools 2(4):1–13.