AG 1, AG 2, AG 3, AG 4, AG 5, SWS, RG1, MMCI   Info

Public Audience

English

60 Minutes

Saarbrücken

In the first part of this thesis, we study the fundamental problem of
sampling from a discrete probability distribution. Specifically, given
non-negative numbers p_1,...,p_n the task is to draw i with probability
proportional to p_i. We extend the classic solution to this problem,
Walker's alias method, in various directions: We improve its space
requirements, we solve the special case of sorted input, we study
sampling natural distributions on a bounded precision machine, and as an
application we speed up sampling a model from physics.

The second part of this thesis belongs to the area of computational
geometry and deals with algorithms for the Fréchet distance, which is a
popular measure of similarity of two curves and can be computed in
quadratic time (ignoring logarithmic factors). We provide the first
conditional lower bound for this problem: No polynomial factor
improvement over the quadratic running time is possible unless the
Strong Exponential Time Hypothesis fails. We also present an improved
approximation algorithm for realistic input curves.

Christina Fries

--email hidden

passcode not visible

logged in users only