# Events

## Talk given by Prof. Martin Dietzfelbinger (Technische Universität Ilmenau)

Begin: Wed, 16. of Oct 2013 ( 2:00 PM)Location: Fürstenallee 11, Room F1.110

On October 16, 2013, Prof. Martin Dietzfelbinger will give a talk on "Tight Lower Bounds for Greedy Routing in Higher-Dimensional Small-World Grids".

Abstract:

We consider Kleinberg's celebrated small world graph model, in which a
D-dimensional grid $\{0,\dots,n-1\}^D$ is augmented with a constant
number of additional unidirectional edges leaving each node. These long
range edges are determined independently at random according to a
probability distribution (the augmenting distribution), which is the
same for each node. Kleinberg suggested using the inverse D-th power
distribution, in which node v is the long range contact of node u with a
probability proportional to $\|u-v\|_2^{-D}$. He showed that this makes
it possible to route messages efficiently by the greedy strategy: always
move the message over a link that brings it closest to the target w.r.t.
the Manhattan distance. The expected length of the path found is O((log
n)^{2}).

We prove that for fixed D>=2 greedy routing does not perform
asymptotically better for any uniform and isotropic augmenting
distribution, i.e., the probability that node u has a particular long
range contact v only depends on $\|{u-v}\|_2$. (Before this was known
only for D=1.)

For the proof we define a so-called budget game, in which a token
travels over a one-dimensional game board from one end to the other,
while the player manages a "probability budget". In each round, the
player "bets" part of her remaining probability budget on step sizes.
The token makes progress by a step size chosen at random according to
the player's bet, and depending on this progress, some of the player's
bet is removed from her probability budget. We prove a tight lower bound
on the expected number of rounds needed in this game. The lower bound
for greedy routing in the D-dimensional grid follows by a reduction.

(joint work with Philipp Woelfel, University of Calgary)