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. |
|---|
| Abstract: |
|---|
| 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 |
|---|
