Lectures and Colloquia during the semester

Montag, 5. Februar 2001

Freie Universität Berlin - Institut für Informatik
Takustraße 9, 14195 Berlin
Seminarraum 005

Lecture - 14.00 Uhr c.t.

Jürg Nievergelt - ETH Zürich

Exhaustive search, combinatorial optimization and enumeration:
Exploring the potential of raw computing power

Abstract: For half a century since computers came into existence, the goal of finding elegant and efficient algorithms to solve "simple" (well-defined and well-structured) problems has dominated algorithm design. Over the same time period, both processing and storage capacity of computers have increased by roughly a factor of a million. The next few decades may well give us a similar rate of growth in raw computing power, due to various factors such as continuing miniaturization, parallel and distributed computing. If a quantitative change of orders of magnitude leads to qualitative advances, where will the latter take place? Only empirical research can answer this question.

Asymptotic complexity theory has emerged as a surprisingly effective tool for predicting run times of polynomial-time algorithms. For NP-hard problems, on the other hand, it yields overly pessimistic bounds. It asserts the non-existence of algorithms that are efficient across an entire problem class, but ignores the fact that many instances, perhaps including those of interest, can be solved efficiently. For such cases we need a complexity measure that applies to problem instances, rather than to over-sized problem classes.

Combinatorial optimization and enumeration problems are modeled by state spaces that usually lack any regular structure. Exhaustive search is often the only way to handle such "combinatorial chaos". Several general purpose search algorithms are used under different circumstances. We describe reverse search and illustrate this technique on a case study of enumerative optimization: enumerating the k shortest Euclidean spanning trees.

Colloquium - 16 Uhr s.t.

Stefan E. Schmidt -New Mexico State University

Block Space-Time Codes in Wireless Communication

Abstract: We construct and analyse block space-time codes with low decoding complexity. For a given number of transmit antennas, the codes have maximum diversity and good coding gain. Tradeoffs between information rate, diversity, delay and decoder complexity are also presented. These are the best known results to date and are applicable for arbitrary signal constellations in the complex plane. We point out the impact of the subject in wireless communcation.

The mathematical side of our work involves orthogonal designs and matrix representations of algebraic structures like the quaternions, octonions, and Clifford algebras.

The talk is based on a current research project together with Paul E. Wright, which we began almost two years ago at the Shannon Laboratory of AT&T.