Two PhD student positions in Theoretical Computer Science, München (Germany)

Modern computers have faster and faster CPUs, such that it is getting more and more difficult to supply them with the data bandwidth to leverage this speed. This works reasonably well if data is accessed linearly, and basically impossible if memory accesses are random. Hence, to help the design of fast algorithms, it is useful to consider the so called I/O-model, that captures the data transfer between different types of memory like cache and main memory.

In this setting the project is concerned with the multiplication of a dense vector with a sparse matrix. This is not only an important building block of many applications, but also an abstract formulation of a data-flow problem. The focus is to understand the influence of the structure in the non-zero entries of the matrix on the I/O-complexity of the problem.

The preferred starting time for the positions is September. Applications are expected to arrive by July 22. Further information is available at http://www14.in.tum.de/personen/jacob/group.html.en or directly from Riko Jacob, jacob at in.tum.de