De Computability.

Version du 13 janvier 2011 à 12:23

Ce groupe de travail informel organisé au LIAFA 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.

Horaire et lieu

Le séminaire a lieu le mercredi à partir de 16h, en salle 5C03 (au 5éme étage) au 175 rue du Chevaleret, 75013 Paris (voir ici pour l’accès au LIAFA).

Prochains exposés

Exposés récents

• 12 Janvier 2011: On Sampling, Searching and Kolmogorov complexity (by Scott Aaronson).

Orateur: Andrei Romashchenko (LIF, Marseille)

In computational complexity we mostly deal with decision problems: given an input x we must decide whether x belongs to some (fixed in advance) set A. However there are other natural types of problems: promise, searching, sampling problems... In this talk we will consider mostly the relation between search problems and sampling problems.

In a search problem, we must obtain from an input x of length n some member y of a nonempty set A(x). In a sampling problem, we are given an input x of length n, and asked to sample (at least approximately) from a probability distribution D(x) over poly(n)-bit strings. It turns out that these types of problems are equivalent in some sense. E.g., it follows that classical algorithms can efficiently sample the output distribution of every quantum circuit, if and only if classic computers can solve in polynomial time every search problem that quantum computers can effectively solve.

The proposed by Aaronson reduction between these types of problems is based on a very nice application of Kolmogorov complexity.

• 5 Janvier 2011: On the problem of synchronizing remote files

Orateur: Andrei Romashchenko (LIF, Marseille)

We consider the following communication problem. Let Alice and Bob have strings X and Y of length N, and Hamming distance these strings is bounded by $\alpha N$ (for some $\alpha<1/2$). Alice and Bob can communicate to each other by a channel. Alice wants to transmit her string X to Bob. How to do it with minimal number of bits sent through the channel ?

We will consider different formal models of this problem and the best known solutions. (Results of A. Orlitsky, A. Smith, and others.)

• 1er décembre 2010: Low Turing degrees: examples, constructions and applications

Orateur: Laurent Bienvenu (LIAFA, Paris 7)

Last time we ended the session with the construction of a low c.e. degree with priority arguments. In this talk, we will further study the class of low degrees. We will show that every c.e. set can be split into a pair of low degrees. We will also present the fundamental "low basis theorem" which asserts that every non-empty effectively closed set (in the Cantor space) contains a low member. We will demonstrate the power of this technique by presenting the Nies-Stephan-Terwijn characterization of 2-randomness via Kolmogorov complexity [caveat: unlike the previous sessions, some prior knowledge of basic notions of algorithmic randomness is required (plain and prefix Kolmogorov complexity, Martin-Löf randomness, Chaitin's Omega numbers)].

• 24 novembre 2010: Priority arguments in computability theory: part 1

Orateur: Laurent Bienvenu (LIAFA, Paris 7)

It is well-known that the halting problem for Turing machines is undecidable, but computably enumerable. In fact, the halting problem is complete among computably enumerable set: if we are given the solution of halting problem on a an infinite tape, we can use it to decide any computably enumerable set. In the 1940's, Post asked whether there exists an intermediate computably enumerable problem, i.e. one that is not decidable but cannot solve the halting problem. The answer came after more than 10 years, from the independent work of Friedberg and Muchnik, via what we now call a priority argument with finite injury. We will discuss the proof of this theorem and if time permits we will see how the finite injury technique can be used to prove more advanced computability theorem. The (much) more complicated techniques involving priority with infinite injury will be presented in a later talk.

• 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.

• 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 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.

Contacts

• Laurent Bienvenu
• Antoine Taveneaux