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
