Vendredi 27/01/2017, 11h, B107 : Borne inf PARITY
Bonjour, Finalement avec Flavien on a décidé de nous lancer sans hésitations dans les circuits booléens, donc *demain*, vendredi 27 janvier 2017, à 11h en B107, on fera une petite séance de groupe de travail concernant la borne inf sur PARITY, un résultat classique de complexité, prouvé dans les années 80 indépendemment par Ajtai et Furst-Saxe-Sipser, qui était, avant le résultat de Williams de 2010, à peu près la seule séparation non-triviale de classe de circuits connue. Le gdt ne sera pas long : on n'a pas grande chose à raconter, je connais l'idée de la preuve mais je ne comprends pas les détails techniques, c'est un peu pour ça que j'ai lancé l'idée de ce groupe de lecture/trvail. À demain, Damiano
Bonjour, Argh! On venait de dire que demain il n’y avait pas de GdT et moi j’ai pris un autre rendez-vous. Je ne sais pas si j’arrive à me libérer. Damiano ou Flavien, pouvez-vous envoyer des références sur ce dont vous allez parler demain? A+ —s ===================================== Stefano Guerrini Président du Département d'Informatique Institut Galilée, Université Paris 13, Sorbonne Paris Cité Responsable Équipe LCR (Logique, Calcule et Raisonnement) Laboratoire d'Informatique de Paris-Nord (LIPN), CNRS (UMR 7030) stefano.guerrini@univ-paris13.fr <mailto:stefano.guerrini@univ-paris13.fr>
On 26 Jan 2017, at 15:25, Damiano Mazza <damiano.mazza@lipn.univ-paris13.fr> wrote:
Bonjour,
Finalement avec Flavien on a décidé de nous lancer sans hésitations dans les circuits booléens, donc
*demain*, vendredi 27 janvier 2017, à 11h en B107,
on fera une petite séance de groupe de travail concernant la borne inf sur PARITY, un résultat classique de complexité, prouvé dans les années 80 indépendemment par Ajtai et Furst-Saxe-Sipser, qui était, avant le résultat de Williams de 2010, à peu près la seule séparation non-triviale de classe de circuits connue.
Le gdt ne sera pas long : on n'a pas grande chose à raconter, je connais l'idée de la preuve mais je ne comprends pas les détails techniques, c'est un peu pour ça que j'ai lancé l'idée de ce groupe de lecture/trvail.
À demain,
Damiano
_______________________________________________ Gdtlogprog mailing list Gdtlogprog@lipn.univ-paris13.fr https://www-lipn.univ-paris13.fr/mailman/listinfo/gdtlogprog
!DSPAM:78,588a06de127851222118493!
Ne t'inquiète pas pour demain, ce sera probablement une discussion préliminaire et on fera une deuxième séance par la suite. On pourrait d'ailleurs imaginer d'inviter des membres de CALIN, c'est des trucs qui leur plaisent (et qu'ils connaissent peut-être !). Pour les références : Je vous joins les articles originaux d'Ajtai et de Furst, Saxe et Sipser. Leur preuve (formulé dans deux contextes différents mais basée essentiellement sur la même idée) a été amélioriée par la suite ; aujourd'hui on a des résultats pratiquement optimaux utilisant le fameux "switching lemma" de Håstad, qui est le coeur de la preuve telle qu'on la présente aujourd'hui. Le texte "classique" Arora, Barak "Computational Complexity - A Modern Approach", Cambridge University Press, 2009 présente cette preuve, pas forcement de manière très compréhensible (moi, je me perds genre à la 5ème ligne). Si vous voulez des alternatives, tapez hastad switching lemma dans Google et vous aurez une liste d'une dizaine de PDF explicant, chacun à sa façon, la preuve. Il s'agit pour la plupart de poly de cours, car c'est un résultat tellement classique et important qu'il est enseigné dans n'importe quel cours (un minimum avancé) de complexité, et donc chaque enseignant a sa façon de le voir, sa façon de l'expliquer, etc. Malgré cela, je n'en ai trouvé *aucun* donnant une preuve que j'arrive à suivre jusqu'au bout (c'est sans doute moi qui suis un peu trop réfractaire à la méthode probabiliste). Damiano On 26/01/2017 15:33, Stefano Guerrini wrote:
Bonjour,
Argh! On venait de dire que demain il n’y avait pas de GdT et moi j’ai pris un autre rendez-vous. Je ne sais pas si j’arrive à me libérer.
Damiano ou Flavien, pouvez-vous envoyer des références sur ce dont vous allez parler demain?
A+
—s
=====================================
Stefano Guerrini Président du Département d'Informatique Institut Galilée, Université Paris 13, Sorbonne Paris Cité Responsable Équipe LCR (Logique, Calcule et Raisonnement) Laboratoire d'Informatique de Paris-Nord (LIPN), CNRS (UMR 7030) stefano.guerrini@univ-paris13.fr <mailto:stefano.guerrini@univ-paris13.fr>
On 26 Jan 2017, at 15:25, Damiano Mazza <damiano.mazza@lipn.univ-paris13.fr <mailto:damiano.mazza@lipn.univ-paris13.fr>> wrote:
Bonjour,
Finalement avec Flavien on a décidé de nous lancer sans hésitations dans les circuits booléens, donc
*demain*, vendredi 27 janvier 2017, à 11h en B107,
on fera une petite séance de groupe de travail concernant la borne inf sur PARITY, un résultat classique de complexité, prouvé dans les années 80 indépendemment par Ajtai et Furst-Saxe-Sipser, qui était, avant le résultat de Williams de 2010, à peu près la seule séparation non-triviale de classe de circuits connue.
Le gdt ne sera pas long : on n'a pas grande chose à raconter, je connais l'idée de la preuve mais je ne comprends pas les détails techniques, c'est un peu pour ça que j'ai lancé l'idée de ce groupe de lecture/trvail.
À demain,
Damiano
_______________________________________________ Gdtlogprog mailing list Gdtlogprog@lipn.univ-paris13.fr <mailto:Gdtlogprog@lipn.univ-paris13.fr> https://www-lipn.univ-paris13.fr/mailman/listinfo/gdtlogprog
!DSPAM:78,588a06de127851222118493!
Pour ceux qui sont intéressés, on est dans le bureau de Paulin (A203). On n'est que 3 donc pour l'instant ce n'est pas la peine d'aller en B107. Damiano On 26/01/2017 15:25, Damiano Mazza wrote:
Bonjour,
Finalement avec Flavien on a décidé de nous lancer sans hésitations dans les circuits booléens, donc
*demain*, vendredi 27 janvier 2017, à 11h en B107,
on fera une petite séance de groupe de travail concernant la borne inf sur PARITY, un résultat classique de complexité, prouvé dans les années 80 indépendemment par Ajtai et Furst-Saxe-Sipser, qui était, avant le résultat de Williams de 2010, à peu près la seule séparation non-triviale de classe de circuits connue.
Le gdt ne sera pas long : on n'a pas grande chose à raconter, je connais l'idée de la preuve mais je ne comprends pas les détails techniques, c'est un peu pour ça que j'ai lancé l'idée de ce groupe de lecture/trvail.
À demain,
Damiano
_______________________________________________ Gdtlogprog mailing list Gdtlogprog@lipn.univ-paris13.fr https://www-lipn.univ-paris13.fr/mailman/listinfo/gdtlogprog
participants (2)
-
Damiano Mazza -
Stefano Guerrini