Lectures and Colloquia during the semester

**July 9, 2001**

Freie Universität Berlin - Institut für
Informatik

Takustraße 9, 14195 Berlin

Room 005

**Lecture - 14:15**

### Johannes Blömer - Universität Paderborn

### Grids and Cryptography

*Abstract:*
Grids and cryptography are connected in two ways. On the one hand
grid problems can be used to design cryptographic methods.
On the other hand the LLL-algorithm for computing the shortest vector
in a grid is one of the most important tools in the cryptoanalysis of
many cryptographic methods. In the talk we will elaborate on both
aspects. We will consider the complexity of computing the successive
minima of a grid. This problem is the basis of an encryption method
suggested by Ajtai some years ago. The average complexity of
Ajtai's method corresponds to the worst-case complexity of computing
the last successive minimum of a grid.
In the second part of the lecture we will explain how the LLL-algorithm
can be used to crack certain variants of the RSA-algorithm.

**Colloquium - 16:00**

### Otfried Cheong - Utrecht

### Paths with bounded curvature

*Abstract:*
Motion planning with non-holonomic constraints, such as the
restriction on the radius of curvature natural for car-like robots, is
of considerable practical interest, but even simple theoretical
questions turn out to be quite hard. We discuss some fundamental
results on bounded curvature paths that can be applied to robot motion
planning. In particular, we characterize the region of all points
inside a convex polygon that can be reached by a bounded-curvature
robot from a given starting configuration. We also show that no robot
can effectively visit a sequence of points that are given on-line
(that is, one by one) using a bounded curvature path, while giving an
algorithm to compute a short path if the whole sequence is given in
advance.

(Joint work with Hee-kap Ahn, Kyung-Yong Chwa, Jae-Ha Lee, Jiri
Matousek, Woo-Cheol Kwon, Sung-Yong Shin, and Antoine Vigneron)

[top]