max planck institut

informatik

informatik

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.

Evolutionary algorithms gained significant attention in the last 20 or so years. Practitioners love them for being simple, cheaply to implement and robust algorithms that often yield surprisingly good results. Unfortunately, a theoretical understanding of these methods 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 search 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.

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 (quite a while ago) for 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 than n. Many
related questions are still open and would make a nice thesis topic.

Imagine a node of a network having a piece of information ('rumor') to be disseminated
to all nodes. A 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 papers (consult my
publication page), but of
course for a thesis there are also less technical questions available.

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 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 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.

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?