27 Mars - 2 Avril


Retour à la vue des calendrier
Mardi 28 Mars
Heure: 14:00 - 17:00
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Phase Transition Threshold for Random Graphs and 2-SAT using Degree Constraints
Description: Sergey Dovgal We show that by restricting the degrees of the vertices of a graph to an arbitrary set ?, the threshold ?(?) of the phase transition for a random graph with n vertices and m = ?(?).n edges can be either accelerated (e.g.,?(?) approx 0.38 for ? = {0,1,4,5}) or postponed (e.g., ?(?) approx 0.95 for ?={1,2,50}) compared to a classical Erd?s?Rényi random graph where ?(N)=1/2. We investigate different graph statistics inside the critical window of transition (planarity, diameter, longest path...).We apply our results to a 2-SAT model with restricted literal degrees: the number of clauses that each literalis incident to belongs to the set ?. We prove a lower bound for the probability that a formula with n variables and m=2.?(?) n clauses is satisfiable. This probability is close to 1 for the subcritical regime m=2.?.n.(1-μ.n-1/3), μ to ∞ and improves/generalizes the lower bound of Bollobás, Borgs, Chayes, Kim, and Wilson.This shows how the phase transition threshold for 2-SAT moves if we change the degrees of the literals.Joint work with Vlady Ravelomanana.
Vendredi 31 Mars
Heure: 11:00 - 12:30
Lieu: Salle B107, bâtiment B, Université de Villetaneuse
Résumé: Équivalences entre programmes
Description: Jean-Yves Moyen Partant du théorème de Rice, on définit l'équivalence extensionelle comme "deux programmes sont équivalents si ils calculent la même fonction." Le théorème de Rice stipule alors une indécidabilité forte de cette équivalence (aucune union de classes n'est décidable).

Qu'en est-il des autres équivalences entre programmes ? Certaines sont décidables (eg, avoir le même nombre de lignes de codes), d'autres non. L'ensemble des équivalences possède une structure de treillis complet et le théorème de Rice parle de l'indécidabilité d'un filtre principal de ce treillis.

À partir de ces constatations, j'explore deux pistes parallèles. D'une part, quelle est l'importance de l'équivalence extensionelle dans ces résultats ? Est-ce qu'on peut obtenir d'autres résultats similaires à partir d'une autre équivalence ? D'autre part, comment étudier l'ensemble du treillis des équivalences ? Est-ce qu'on peut trouver des sous-ensembles qui conservent la structure lié à l'ordre tout en étant plus facilement manipulables (notamment, dénombrables) ?