unbekannter Gast
Geben Sie diesem Artikel Ihre Stimme:
5

Track 1: Foundations and Theory
#

Aichholzer
Chairperson O. Aichholzer


Welzl Emo: Counting of Crossing-Free Geometric Graphs
#

The structure of crossing free geometric graphs of various types (triangulations, spanning trees or cycles, all such graphs, etc.) on a given finite planar point set remains elusive despite of some efforts. We report on some moderate progress obtained recently, among others on the extremal numbers and on the counting of' the number of such graphs for a point set.

About Emo Welzl

Welzl.jpg
Emo Welz
Born in Linz, Austria, Diplom in Applied Mathematics at the Graz University of Technology, Austria. 1983 Ph.D. (supervisor Hermann Maurer) with a topic in formal languages, 1988 habilitation (second Ph.D.) in Foundations of Computer Science, also in Graz. 1984 one-year post-doc at Rijks University Leiden, Netherlands, 1985 visiting professor at the University of Denver, Colorado, USA, for one semester. 1987-1996 Full Professor of Mathematics (theory of computation) at Free University of Berlin. 1994 four-month research stay at the International Computer Science Institute, Berkeley, California, USA. 1991-1996 chair of the graduate program "Computational Discrete Mathematics" at Free University, Humboldt University, University of Technology, and the Konrad Zuse Center in Berlin. 2000-2005 chair (at site Zurich) of the Berlin-Zurich Graduate Program in "Combinatorics, Geometry, and Computation".

Emo Welzl has been Full Professor of Computer Science at the Institute for Theoretical Computer Science of the ETH Zurich since April 1996.

His research interests are in the foundations of computer science, mainly algorithms and data structures, in particular computational geometry and applications, combinatorial models for optimization, analysis of geometric structures, randomized methods, and discrete geometry.

He was awarded with many prizes (among them Max Planck Prize, Gottfried Wilhelm Leibniz-Prize) and is Fellow of the Association for Computing Machinery and Member of the German Academy of Sciences Leopoldina and of the Academia Europaea. Editorial board member of numerous journals and member of many program committees


Calude Cristian: Most Programs Stop Quickly or Never Halt
#

The aim of this talk is to provide a probabilistic, but non-quantum, analysis of the Halting Problem. Our approach is to have the probability space extend over both space and time and to consider the probability that a random N-bit program has halted by a random time. We postulate an a priori computable probability distribution on all possible runtimes and we prove that given an integer k>0, we can effectively compute a time bound T such that the probability that an N-bit program will eventually halt given that it has not halted by T is smaller than 2^{-k}. We also show that the set of halting programs (which is computably enumerable, but not computable) can be written as a disjoint union of a computable set and a set of effectively vanishing probability. Finally, we show that "long" runtimes are effectively rare. More formally, the set of times at which an N-bit program can stop after the time 2^{N+constant} has effectively zero density.

About Cristian S. Calude

Calude
Born in Galatzi, Romania, he studied at Bucharest University, received the BSc (Hons) in Mathematics and Computer Science, 1975, PhD, 1977.
After being Professor at the Bucharest University, Romania, he moved to New Zealand, where he is Chair Professor of Computer Science, Computer Science Department (from April 1994 on) and Director of the Centre for Discrete Mathematics and Theoretical Computer Science (from 1995 on).
He also is an Associate Member of the International Solvay Institutes, Brussels Free University, Brussels, Belgium; an Associate Researcher at Canterbury University, Christchurch, New Zealand, an Research Associate and Member of the Council at the Centre for Logic and Informatics Bucharest, Romania, and a Honorificum Membrum, Black Sea University, Bucharest, Romania.


Seidel Raimund: n Lines - n squared intersections - Subquadratic Time
#

In the plane n lines in general induce a quadratic number of intersection points. What kind of computational problems on this set of intersection points can be solved in subquadratic time? I will show that computing the center of mass is among them, and I will discuss some related problems.

About Raimund Seidel

Seidel
Raimund Seidel was born in Graz and after his school education in Graz, Austria, and Hudson, Wisconsin, USA, he studied Mathematics and Computer Science at the Graz University of Technology, Austria, the University of British Columbia in Vancouver, Canada, and at the Cornell University in Ithaca, New York, USA.
He was guest researcher at DEC Systems Research Center and at IBM Almaden Research Center and from 1986 till 1996 he was Assistant- and then Associate-Professor in the Computer Science Division of the University of California, Berkeley.

Since 1994 Prof. Dr. Raimund Seidel holds the Chair of Theoretical Computer Science at the Department of Computer Science at Saarland University.

His main research interests are algorithms theory, analysis of efficient algorithms and data structures, especially for geometric problems, and randomization.


Rote Günter: Collapse
#

We can simulate the collapse of an unstable tower of bricks, following Newton's laws. The accelerations of the bricks are determined by a quadratic programming problem with linear side constraints.

About Günter Rote

Rote
Born 1960 in Klagenfurt, Austria, diploma in technical mathematics at Graz University of Technology, Austria. 1988 Ph.D. (supervisor Rainer Burkard) about solvable cases of the Traveling Salesman Problem, 1992 habilitation in mathematics, also in Graz.
1985-1999 assistant (professor) and associate professor at TU Graz, department of mathematics, 1989 post-doc at FU Berlin, 1990 visiting assistant professor in Waterloo, Canada, for one semester.
Günter Rote is full professor of theoretical computer science at Freie Universität Berlin, Germany, since 1999.

His research interests are in the design of efficient algorithms, in particular in computational geometry and discrete optimization. He has written no books. Jointly with Bob Connelly and Erik Demaine, he solved the Carpenter's Rule Problem about unfolding of polygonal linkages, and with Wolfgang Mulzer, he has recently established the NP-hardness of the minimum-weight triangulation problem.


Continue to Track 2