Exposés récents
De Computability.
(Différences entre les versions)
m (a déplacé Exposés recents vers Exposés récents) |
|||
| Ligne 1 : | Ligne 1 : | ||
* '''10 Novembre 2010: The entropy compression argument, Lovasz local lemma and Kolmogorov complexity''' | * '''10 Novembre 2010: The entropy compression argument, Lovasz local lemma and Kolmogorov complexity''' | ||
:'''''Orateur: Alexander Shen (LIF, Marseille)''''' | :'''''Orateur: Alexander Shen (LIF, Marseille)''''' | ||
| - | :One of the classical applications of Kolmogorov | + | :One of the classical applications of Kolmogorov complexity to computational complexity and algorithms is the so called ''incompressibility method''. This method is useful to prove lower bounds on the complexity of a problem by considering an instance of high Kolmogorov complexity and argue that for that particular instance the problem is "hard". In this talk, we present a recent new application of Kolmogorov complexity: the ''entropy reduction method'' due to Moser and Tardos. This technique is used to prove the termination of a randomized algorithm when the algorithm is "reversible" in a weak sense. This powerful technique can be applied to prove a constructive version of Lovasz local lemma (a central theorem in combinatorics), which we will discuss if time permits. |
Version actuelle en date du 14 novembre 2010 à 23:01
- 10 Novembre 2010: The entropy compression argument, Lovasz local lemma and Kolmogorov complexity
- Orateur: Alexander Shen (LIF, Marseille)
- One of the classical applications of Kolmogorov complexity to computational complexity and algorithms is the so called incompressibility method. This method is useful to prove lower bounds on the complexity of a problem by considering an instance of high Kolmogorov complexity and argue that for that particular instance the problem is "hard". In this talk, we present a recent new application of Kolmogorov complexity: the entropy reduction method due to Moser and Tardos. This technique is used to prove the termination of a randomized algorithm when the algorithm is "reversible" in a weak sense. This powerful technique can be applied to prove a constructive version of Lovasz local lemma (a central theorem in combinatorics), which we will discuss if time permits.
