Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society

MPI-INF or MPI-SWS or Local Campus Event Calendar

<< Previous Entry Next Entry >> New Event Entry Edit this Entry Login to DB (to update, delete)
What and Who
Title:PhD Defense Karl Bringmann
Speaker:Karl Bringmann
coming from:Max-Planck-Institut für Informatik - D1
Speakers Bio:
Event Type:Promotionskolloquium
Visibility:D1, D2, D3, D4, D5, SWS, RG1, MMCI
We use this to send out email in the morning.
Level:Public Audience
Date, Time and Location
Date:Wednesday, 17 December 2014
Duration:60 Minutes
Building:E1 4
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.
Name(s):Christina Fries
Video Broadcast
Video Broadcast:NoTo Location:
Tags, Category, Keywords and additional notes
Attachments, File(s):
  • Christina Fries, 12/08/2014 02:05 PM -- Created document.