Groupe de travail Calculabilité, Complexité et Hasard
De Computability.
(modifs reste) |
(version anglaise) |
||
| Ligne 1 : | Ligne 1 : | ||
[[Fichier:English_Language.png|55px|gauche||link=workshop in computability, complexity and randomness]] '''[[workshop in computability, complexity and randomness| Click here for the English version ]]''' | [[Fichier:English_Language.png|55px|gauche||link=workshop in computability, complexity and randomness]] '''[[workshop in computability, complexity and randomness| Click here for the English version ]]''' | ||
| + | This informal reading group aims at providing a forum for exchange of ideas on a certain number of topics, in particular: | ||
| + | * computability theory | ||
| + | * models of computation | ||
| + | * algorithmic complexity | ||
| + | * algorithmic randomness (Kolmogorov complexity, Martin Löf randomness, etc) | ||
| + | * pseudo-randomness theory (expanders, extractors, etc) | ||
| + | * any topic related to the one of the above | ||
| - | + | As opposed to a "standard" seminar, speakers are encouraged to present one or several theorems (with their proofs!), a classical technique, an important idea (not necessarily from their own work) rather than give an overview of their last technical paper. There is not strict time limit for talks, even though it would be preferable to not go over the hour and a half (if a talk is taking too long, it can be continued the following week). A shorter talk can also be followed by a discussion between participants, either on the topic of the talk or on any other topic. | |
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | + | ||
| - | |||
| + | =Time and place= | ||
| + | The reading group takes place on Wednesdays starting from 4pm, in room 5C12 (5th floor) at 175 rue du Chevaleret, 75013 Paris ([http://www.liafa.jussieu.fr/web9/acces/acces_fr.php click here for directions LIAFA]). | ||
| - | |||
| - | + | =Upcoming talks= | |
| - | + | * '''November 10, 2010: The entropy compression argument, Lovasz local lemma and Kolmogorov complexity''' | |
| - | + | :'''''Speaker: Alexander Shen (LIF, Marseille)''''' | |
| - | + | ||
| - | * '''10 | + | |
| - | :''''' | + | |
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. | 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. | ||
| - | = | + | =Recent talks= |
| - | = | + | =Contact= |
* [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 à 17:16
This informal reading group aims at providing a forum for exchange of ideas on a certain number of topics, in particular:
- computability theory
- models of computation
- algorithmic complexity
- algorithmic randomness (Kolmogorov complexity, Martin Löf randomness, etc)
- pseudo-randomness theory (expanders, extractors, etc)
- any topic related to the one of the above
As opposed to a "standard" seminar, speakers are encouraged to present one or several theorems (with their proofs!), a classical technique, an important idea (not necessarily from their own work) rather than give an overview of their last technical paper. There is not strict time limit for talks, even though it would be preferable to not go over the hour and a half (if a talk is taking too long, it can be continued the following week). A shorter talk can also be followed by a discussion between participants, either on the topic of the talk or on any other topic.
Sommaire |
Time and place
The reading group takes place on Wednesdays starting from 4pm, in room 5C12 (5th floor) at 175 rue du Chevaleret, 75013 Paris (click here for directions LIAFA).
Upcoming talks
- November 10, 2010: The entropy compression argument, Lovasz local lemma and Kolmogorov complexity
- Speaker: Alexander Shen (LIF, Marseille)
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.
