Benjamin Doerr: Topics for Theses

Below I sketch some areas where I currently have interesting topics for bachelor, master, diploma or PhD projects. Unless otherwise indicated, all areas allow projects on all levels. The descriptions naturally do not give every detail. For more precise information, please contact me. Also, note that the list is not necessarily complete. If you have other ideas that roughly qualify as discrete maths, algorithms or complexity theory, please contact me.

Theory of Evolutionary Algorithms

Evolutionary algorithms gained significant attention in the last 20 or so years. Practitioners love then for being simple, cheaply to implement and robust algorithms that often yield surprisingly good results. Unfortunately, a theoretical understanding of this is still far away. However, in the last few years more and more results popped up that provide rigorous theoretical analyses of such algorithms. Similar statements are true for related randomized seach heuristics like ant colony optimization, particle swarm optimization or simulated annealing. Besides many tempting theoretical questions we do also have some very applied ones in this context.

Combinatorial Games and Black-Box Complexity

A thesis in combinatorial game theory is a way to simultaneously (i) have good fun, (ii) do serious research and (iii) obtain results that have applications in computer science or engineering. Consult this page of a seminar I gave for slighly more information.

A recent research topic in our group is black-box complexity. Inspired by randomized search heuristics, we ask how many function evaluations are necessary to find the optimum of an unknown function from a given class. For the OneMax function class, this is equivalent to the following guessing game:
I decide on a bit-string of length n and you try to guess it. For each guess I tell you the number of bit positions that are correct (but of course not which positions these are). How many guesses do you need? Surprisingly, you can do it with less then n. Many related questions are still open and would make a nice thesis topic.

Randomized Rumor Spreading and Other Epidemic Algorithms

Imagine a node of a network having a piece of information ('rumor') to be disseminated to all nodes. I simple protocol is the following: In each round, each node knowing the rumor calls a random neighbor and forwards a copy of the rumor to it.
Surprisingly, this simple epidemic algorithm is very efficient. For complete graphs, a logarithmic number of rounds suffices. This is optimal in the sense that any protocol with nodes communicating with one neighbor per round need a logarithmic number of rounds.
Our current research interest is making such algorithms even more efficient by not choosing all communication partners independently at random, but allowing a little more cleverness. Two examples of how this can work are my ICALP 2011 and STOC 2011 paper (consult my publication page), but of course for a thesis there are also less technical questions available.

Multi-color Discrepancies

A hypergraph is nothing more than a ground set ('vertices') together with some subsets thereof ('hyperedges'). The discrepancy problem for hypergraphs is to color the vertices with a fixed number of colors in such a way that (as good as possible) each hyperedge contains the same number of vertices in each color. Until very recently, this problem was only investigated for two colors [where it is already highly interesting]. Recent results of different authors indicated that many classical 2-color results have some kind of analogue for arbitrary numbers of colors. In [Doerr, The hereditary discrepancy is nearly independent of the number of colors, Proc. Amer. Math. Soc. 134 (2004)] some explanation of this phenomenon is given. Still there is some more work to be done in this problem field. If you're missing the application, you can also have a nice topic from data engineering or parallel and distributed systems. Say you have 2D geographical data such that each data block covers a small aligned square in the grid. You want to store these data blocks on several parallel disks, as this speeds up the data retrieval compared to a single disk (hopefully). To make this work, you should distribute the data wisely, namely in such a way that requests find their data evenly distributed on the disks.

Randomized Rounding [experimental]

Randomized rounding is a simple and powerful primitive in integer linear programming. However, so far it seems that many of its aspects are praised more in the theory community than in the applied sciences. For some particular facets, experimental results seem to be entirely missing.

Contact

If you feel that you might be interested to work in one of the fields described above, or if you are interested in some area that seems to by close to my area of expertise, contact
Prof. Dr. Benjamin Doerr
MPI, Room 304
email: Get email address via email

PS: This was not the recreation you were looking for? OK, try this one. n players, who may discuss their strategies beforehand, are being equipped each with a hat of color red or blue. Each one can see all hats except his own. Simultaneously and without further communication allowed they have to guess their own hat's color. Is there a strategy that guarantees that some players guess right?