November 17 , 2008
Technische Universität Berlin
Fak. II, Institut für Mathematik
Str. des 17. Juni 136
10623 Berlin
room MA 041
Lecture - 14:15
Abstract:
With classical algorithmics naturally being deterministic, it was quite
a revolution when randomized algorithms became highly successful in the
last 30 years.
Nowadays, randomized algorithms are well-established. For many problems,
randomized algorithms are currently the best known solution.
Surprisingly, in most cases these algorithms are quite simple. Often, it
suffices to make all decisions independently at random. However, recent
results suggest that a more careful use of randomness may yield even
superior results.
In the talk, I shall first demonstrate the success of independent
randomized methods. I will then show (i) how to gain improvements by
using the right dose of randomness, and (ii) how one can still analyze
thus random experiments in spite of the dependencies.
Colloquium - 16:00
Abstract:
A finite graph can be viewed, in many respects, as a discrete
analogue of a Riemann surface. We pursue this analogy in the context
of linear equivalence of divisors.
A divisor $D$ on a graph $G=(V,E)$ is a $\Z$-linear combination of
vertices.
$$D = \sum_{v \in V} D(v) \cdot v \quad \in \ \text{ with } D(v) \in
\Z$$
We consider $D$ as a vector in $\R^V$. Then we call two divisors
linearly equivalent, $D \sim D'$, if $D-D' \in \ker L$, where $L
\colon \R^V \to \R^V$ is the Laplace matrix of $G$.
This notion of equivalence can be formulated in terms of
Bj\"orner/Lov\'asz/Shor's chip firing game.
Many classical results on Riemann surfaces have analogues in this
setting. Most notably, there is an analogue of the Riemann-Roch
Theorem [Baker/Norine 2006].
Most of these results can be generalized to ``tropical curves''
which are essentially metric graphs [Gathmann/Kerber 2006,
Mikhalkin/Zharkov 2006, Hladk\'y/Kr\'al'/Norine 2007].
Riemann-Roch is a statement about linear systems of
divisors. Classically, a linear system is a projective space.
Tropically, a linear system is a polyhedral complex which looks like
a tropical polytope, but isn't.
This will be joint work with Josephine Yu and Gregg Musiker (MIT).