Track 1: Foundations and Theory
#
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
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
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
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
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
