Workshop in computability, complexity and randomness
De Computability.
m |
|||
Ligne 21 : | Ligne 21 : | ||
=Upcoming talks= | =Upcoming talks= | ||
- | * ''' | + | * '''17 Novembre 2010: The Moser-Tardos constructive proof of Lovasz Local Lemma''' |
- | :''''' | + | :'''''Orateur: Alexander Shen (LIF, Marseille)''''' |
- | : | + | :Last time we have shown how Kolmogorov complexity can be used to show that depth-first resampling can make a sparse CNF satisfied. However, to come close to Lovasz Local lemma and to show that the order of resampling does not matter, one needs to use more ingenious (but still simple) probabilistic argument that we plan to cover. (No previous knowledge about LLL will be really needed, so formally the talk is independent from the previous one). We also discuss some application to infinite formulas. |
- | + | ||
Version du 14 novembre 2010 à 23:20
Cliquez ici pour la version Française
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
- 17 Novembre 2010: The Moser-Tardos constructive proof of Lovasz Local Lemma
- Orateur: Alexander Shen (LIF, Marseille)
- Last time we have shown how Kolmogorov complexity can be used to show that depth-first resampling can make a sparse CNF satisfied. However, to come close to Lovasz Local lemma and to show that the order of resampling does not matter, one needs to use more ingenious (but still simple) probabilistic argument that we plan to cover. (No previous knowledge about LLL will be really needed, so formally the talk is independent from the previous one). We also discuss some application to infinite formulas.
Recent talks