Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 29 octobre 2013 à 14h00 en B107, Bernhard Gittenberger nous parlera de : Random Boolean functions generated by random Boolean expressions

Résumé : We will investigate the probability distribution on the set of Boolean functions in n variables if a Boolean function is generated by a large Boolean expression drawn uniformly at random from all expressions of the same size. We show that a precise quantitative relation between the probability of a function and its complexity which is defined as the minimal size of an expression representing the function.

 [Slides.pdf]


Dernière modification : lundi 28 octobre 2013 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at lipn.univ-paris13.fr