Lectures and Colloquia during the semester

Freie Universität Berlin - Institut für Informatik

Takustraße 9, 14195 Berlin

Seminarraum 005

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.**

*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.

[top]