Workshop in computability, complexity and randomness

De Computability.

(Différences entre les versions)
m (Upcoming talks)
m (Upcoming talks)
Ligne 21 : Ligne 21 :
=Upcoming talks=
=Upcoming talks=
-
<!-- Ceci est un aide mémoire pour la syntaxe: * ''' th 2011: .'''  
+
<!-- Ceci est un aide mémoire pour la syntaxe:  
 +
* ''' th 2011: .'''  
:'''''Speaker:  ()'''''
:'''''Speaker:  ()'''''
-
: .  -->
+
: .   
 +
-->
=Recent talks=
=Recent talks=

Version du 11 avril 2011 à 22:14

Flag of France.png
Cliquez ici pour la version Française
GroLogoLiafa.jpg


This informal LIAFA 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 5C03 (5th floor) at 175 rue du Chevaleret, 75013 Paris (click here for directions LIAFA).


Upcoming talks

Recent talks

  • April 6th 2011: K-triviality and strong jump traceability.
Speaker: Rupert Hölzl (LIAFA, Paris 7)
This talk will present the recent proof of Downey and Greenberg that strong jump traceability implies K-triviality.


  • March 2nd 2011: A survey of r.e. Turing degree structure: from incomparables to jump inversion theorems.
Speaker: Grégory Lafitte (LIF, Marseille)
We will try to review the structure of the r.e. sets ordered by the Turing reducibility and finish by focusing on various jump inversion theorems.


  • February 16th 2011: A short introduction expander graphs.
Speaker: David Xiao (LIAFA, Paris 7)
Expander graphs are graphs have the paradoxical property of being highly connected but sparse. They are useful throughout computer science and mathematics, especially in areas related to derandomization. In this brief introduction, we will give the definition of expander graphs, show an application of expander graphs to deterministic error reduction, and present the zig-zag construction of expander graphs of Reingold, Vadhan, and Wigderson.


  • February 9th 2011: Functionals using uniformly bounded information and Abstract State Machines.
Speaker: Serge Grigorieff (LIAFA, Paris 7)
Gurevich Abstract State Machines (aka Evolving algebras) model the notion of sequential algorithm on countable data structures as the evolution of some functions on a countable logical structure. This evolution can also be seen as a functional $\Phi$ which, after some identifications and decurryfication, goes from the Baire space $N^N$ to $N$. In this work, in collaboration with Pierre Valarcher, we characterize these functionals as those which are effectively uniformly continuous relative to a particular transitive uniformity compatible with the usual product topology on the Baire space. This uniform continuity of $\Phi$ is equivalent to the existence of some $k$ such that, for all $f\in N^N$, $\Phi(f)$ is completely determined by the values of $f$ on at most $k$ points (depending on $f$). We also show that, up to increasing $k$ to $k^2$, one can define these points as the values of some fixed compositions of $f$ with some fixed functions independent of $f$.


  • February 2nd 2011:Some links between  resource-bounded Kolmogorov complexity and  computational complexity.
Speaker: Antoine Taveneaux (LIAFA, Paris 7)
The concept of Kolmogorov complexity is a powerful tool in computability, it provides natural examples, and can be a good way to characterize some computability classes. In the same way resource-bounded Kolmogorov complexity can be a useful point of view on the computational complexity theory. This lecture will be an informal presentation of some links between  resource-bounded Kolmogorov complexity and  computational complexity.
This lecture will essentially be based on selected  passages of the survey paper “The Pervasive Reach of Resource-Bounded Kolmogorov Complexity in Computational Theory” written by Eric Allender, Michal Koucký, Detlef Ronneburger and Smbuddha Roy.


  • January 26th 2011:Substituting Kolmogorov Sets to Diagonalization.
Speaker: Thomas Hugel (LIAFA, Paris 7)
Hierarchies proofs usually rely on diagonalization arguments. We shall present alternative arguments based on resource-bounded Kolmogorov sets and show some applications to hierarchies among deterministic and advice complexity classes.


  • January 19th 2011:Computability over infinite objects.
Speaker: Mathieu Hoyrup (LORIA, Nancy)
Basic recursion theory provides a robust notion of algorithm over finite, or discrete, objects (natural numbers, finite symbolic sequences, etc.). How to extend this theory to algorithms working on infinite objects such as real numbers, or functions over the natural numbers? Many such extensions have emerged since the work of Turing, but contrary to the discrete case, they have given birth to several non-equivalent models. I will present two closely related models, both based on the Turing machine.
As in the discrete setting, the notion of an algorithm over infinite objects is expressed using a Turing machine that is fed with an input and eventually producing an output, in finite time. But there are (at least) two ways of presenting an infinite object to a Turing machine: (i) it can be progressively described by an oracle, or (ii) if one restricts to computable objects only, those objects can be represented by finite programs, which can be processed by usual Turing machines.
In this talk I will consider the notions of decidable/semi-decidable sets of partial/total functions over the natural numbers. I will present equivalences as well as discrepancies between the two approaches. Along the presentation we will investigate the deep relationship between computability and topology, in particular the topological interpretation of Rice's theorem. The results date back to the 50's.


  • January 12th 2011: On Sampling, Searching and Kolmogorov complexity (by Scott Aaronson)
Speaker: 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.


  • January 5th 2011: On the problem of synchronizing remote files
Speaker: 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.)


  • December 1st, 2010: Low Turing degrees: examples, constructions and applications
Speaker: 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)].


  • November 24, 2010: Priority arguments in computability theory: part 1
Speaker: 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.


  • November 17, 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.


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

Contact

Outils personnels