Date/heure
7 décembre 2023
09:15 - 10:15
Lieu
Salle de conférences Nancy
Oratrice ou orateur
Pierre Mercuriali (IECL)
Catégorie d'évènement Groupe de travail Probabilités et Statistique
Résumé
Je présente ici certains travaux que j’ai effectués lors de ma thèse sur les représentations efficaces de fonctions Booléennes, ainsi que certaines explorations probabilistes que j’ai menées par la suite. Nous pouvons définir une fonction Booléenne {0,1}^n -> {0,1} par sa table de vérité, ce qui est en général plus coûteux que d’en donner une formule, e.g., en forme normale disjonctive ou conjonctive. Je présenterai un cadre de travail général qui permet de comparer, en termes de coût, les différentes manières de définir ces formes normales. La comparaison de certaines formes normales est un problème ouvert. Afin d’y répondre, je présenterai une extension de ce cadre de travail pour étudier la distribution des tailles des formules Booléennes minimales, étant données des contraintes structurelles fortes.