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
|Date:||03 / 19 / 2010|
|Time:||02:30pm - 03:25pm|