Graduiertenkolleg: Methods for Discrete Structures

Deutsche Forschungsgemeinschaft
faculty | junior-faculty | postdocs | students | associate students | former students | former associate students
locations | Term schedule | history
predoc-courses | schools | block-courses | workshops

Monday Lecture and Colloquium

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

Peter Gritzmann - Technische Universität München

On Some New Results in Discrete Tomography

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

Hiep Han - Humboldt Universität zu Berlin

Sparse pseudo-random graphs

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.

Letzte Aktualisierung: 02.05.2007