PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Manfred Denker.

Title:The Lovasz Local Lemma and its effective version
Seminar:Seminar on Probability and its Application
Speaker:Alexander Shen, LIF Marseille and Institute for Information Transmission Problems, Moscow.
The Lovasz local lemma guarantees existence of an object that satisfies several restriction if each restriction deletes a small fraction of objects and they are mostly independent. Its proof is a simple (though ingenious) calculation, but it does not provide a probabilistic algorithm to find the object in question. Recently Robin Moser has found a surprisingly simple alternative argument that provides such a probabilistic algorithm (in most interesting cases). This argument can be explained easily using the basic ideas from Kolmogorov complexity theory.

Room Reservation Information

Room Number:MB106
Date:03 / 19 / 2010
Time:02:30pm - 03:25pm