Groupe de travail Calculabilité, Complexité et Hasard
De Computability.
m |
(modifs reste) |
||
| Ligne 10 : | Ligne 10 : | ||
* tout autre thème connexe aux précédents | * tout autre thème connexe aux précédents | ||
| - | Contrairement à un séminaire "classique", les orateurs sont encouragés à présenter un ou plusieurs théorèmes (avec preuves !), une technique | + | Contrairement à un séminaire "classique", les orateurs sont encouragés à présenter un ou plusieurs théorèmes (avec preuves !), ou une technique classique, une idée importante, plutôt que de présenter les grandes lignes d'un article de recherche récent et pointu. Il n'y a pas de limite stricte sur la durée des exposés, même si l'on essaiera de ne pas trop dépasser l'heure et demie (si un exposé tarde trop, il peut être continué la semaine suivante). Une séance plus courte peut également se continuer par une discussion entre les participants, que ce soit sur le sujet de l'exposé ou sur tout autre sujet. |
| - | |||
| - | |||
| + | =Horaire et lieu= | ||
| - | + | Le séminaire a lieu le mercredi à partir de 16h, en salle 5C12 (au 5éme étage) au 175 rue du Chevaleret, 75013 Paris ([http://www.liafa.jussieu.fr/web9/acces/acces_fr.php voir ici pour l’accès au LIAFA]). | |
| - | |||
| + | =Prochains exposés= | ||
| + | * '''10 Novembre 2010: The entropy compression argument, Lovasz local lemma and Kolmogorov complexity''' | ||
| + | :'''''Orateur: Alexander Shen ''''' | ||
| + | One of the classical applications of Kolmogorov comlexity 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. | ||
| + | =Exposés recents= | ||
| - | |||
| - | |||
| - | + | =Contacts= | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
* [http://www.liafa.jussieu.fr/~lbienven/ Laurent Bienvenu] | * [http://www.liafa.jussieu.fr/~lbienven/ Laurent Bienvenu] | ||
* [http://www.liafa.jussieu.fr/~taveneaux/ Antoine Taveneaux] | * [http://www.liafa.jussieu.fr/~taveneaux/ Antoine Taveneaux] | ||
| - | |||
| - | |||
| - | |||
Version du 7 novembre 2010 à 16:27
Ce groupe de travail informel a pour but de permettre un échange de connaissances et d'idées sur un certains nombre de thèmes, notamment:
- théorie de la calculabilité
- modèles de calcul
- complexité algorithmique
- théorie algorithmique de l'aléatoire (complexité de Kolmogorov, aléatoires au sens de Martin-Löf, etc)
- objets pseudo-aléatoires (expandeurs, extracteurs, etc)
- tout autre thème connexe aux précédents
Contrairement à un séminaire "classique", les orateurs sont encouragés à présenter un ou plusieurs théorèmes (avec preuves !), ou une technique classique, une idée importante, plutôt que de présenter les grandes lignes d'un article de recherche récent et pointu. Il n'y a pas de limite stricte sur la durée des exposés, même si l'on essaiera de ne pas trop dépasser l'heure et demie (si un exposé tarde trop, il peut être continué la semaine suivante). Une séance plus courte peut également se continuer par une discussion entre les participants, que ce soit sur le sujet de l'exposé ou sur tout autre sujet.
Sommaire |
Horaire et lieu
Le séminaire a lieu le mercredi à partir de 16h, en salle 5C12 (au 5éme étage) au 175 rue du Chevaleret, 75013 Paris (voir ici pour l’accès au LIAFA).
Prochains exposés
- 10 Novembre 2010: The entropy compression argument, Lovasz local lemma and Kolmogorov complexity
- Orateur: Alexander Shen
One of the classical applications of Kolmogorov comlexity 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.
