Campus Event Calendar
Event Entry
What and Who
A tutorial on the use of Martingales in randomized algorithms
Surender Baswana
Max-Planck-Institut für Informatik - D 1
Lecture
AG 1, AG 2, AG 3, AG 4, AG 5
AG Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Monday, 15 May 2006
13:30
-- Not specified --
E1 4
024
Saarbrücken
Abstract
Martingales are a well studied concept in classical probability.
In the past few decades, they have also proved to be a very powerful
tool in the analysis of randomized algorithms.
In this tutorial, we shall give a gentle introduction of martingales, highlight their use in randomized algorithm through a couple of examples. The aim of the tutorial is to make us familiar with the use of martingales to the extent we are familiar with Chernoff bound.
Contact
Surender Baswana
833
--email hidden
passcode not visible
logged in users only
Tags, Category, Keywords and additional notes
martingales; randomized algorithms
Surender Baswana, 05/08/2006 11:06 -- Created document.