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.frhttps://www-lipn.univ-paris13.fr/mailman/listinfo/gdtlogprog
!DSPAM:78,588a06de127851222118493!