May 7, 2007
Humboldt-Universität zu Berlin
Institut für Informatik
Rudower Chaussee 25
12489 Berlin
Humboldt-Kabinett, 1st floor, between house III and IV
Lecture - 14:15
Abstract:
Discrete tomography deals with the reconstruction of finite sets from
knowledge
about their interaction with certain query sets. The most prominent example
is that of the reconstruction of a finite subset $F$ of $\mathbb{Z}^d$
from its X-rays (i.e., line sums) in a small positive integer number $m$
of directions.
Applications of discrete tomography include quality control in
semiconductor industry,
image processing, scheduling, and statistical data security.
The reconstruction task is an ill-posed discrete inverse problem, depicting
(suitable variants of) all three Hadamard criteria for ill-posedness.
After a short introduction to the field of discrete tomography,
the first part of the talk addresses the following questions.
Does discrete tomography have the power of error correction? Can noise be compensated by taking more X-ray images, and, if
so, what is the quantitative effect of taking one more X-ray?
Our main theoretical result gives the first nontrivial unconditioned
(and best possible) stability result.
On the algorithmic side we show that while there always
is a certain inherent stability, the possibility of making (worst-case)
efficient use of it is rather limited.
The second part of the talk deals with the discrete tomography of
quasicrystals
that live on finitely generated $\Z$-modules in some $\R^s$..
Focussing on aspects in which the discrete tomography of quasicrystals
differs
from that in the classical lattice case, we solve a basic decomposition
problem
for the discrete tomography of quasicystals. More generally, we study
the problem of
existence of pseudodiophantine solutions to certain systems of linear
equations over
the reals and give a complete characterization of when the index of
Siegel grids is finite.
The results on stability are joint work with Andreas Alpers, Cornell
University, that
on Siegel grids are joint work with Barbara Langfeld, TU Munich. Some other
results on the discrete tomography of quasicrystals presented here are
joint work with
Michael Baake, Christian Huck, Bielefeld, and Barbara Langfeld, Katja
Lord, TU Munich.
Colloquium - 16:00
Abstract:
Random graphs have many desireable properties such as uniform edge
distribution (small discrepancy) or good expansion. Hence capturing the
notion of randomness in a deterministic setting is an important problem,
both from a structural and an algorithmic point of view.
This problem was systematically studied first by Thomason in the mid-80's
and today it's fairly well understood in the case of dense graphs.
In this talk we review some of the classical results in this area
for dense graphs and focus on new results for the sparse case.