Alexis de Colnet (CRIL, Lens)

Etant donné une fonction booléenne F sur n variables et une fonction de poids ρ sur les assignations de variables, on appelle “intégration discrète” (discrete integration) la tâche consistant à calculer le poids de F, défini comme la somme des poids des assignations satisfaisant F. Aussi connu sous le nom “Weighted Model Counting”, le calcul d’une intégrale discrète trouve des applications dans des domaines variés allant du machine learning jusqu’à la physique statistique. Le calcul exact d’une intégrale discrète étant établi comme un problème #P-complet quand ρ est calculable en temps polynomial, les variantes stochastiques ont fait l’objet d’importants efforts tant sur le plan théorique qu’empirique.

Dans cette présentation, j’introduirai en premier le concept d’intégrale discrète ainsi qu’une stratégie pour son calcul approché, laquelle peut être grossièrement résumée par deux étapes : (1) passage de l’intégration discrète au calcul d’intégrales pour les fonctions continues et (2) approximation des intégrales continues via les méthodes usuelles. Je décrirai par la suite deux algorithmes qui appliquent cette stratégie grâce à des fonctions de hachage à base de contraintes de parité : WISH (Weighted Integration & Sum by Hashing) et SWITCH (Sum of Weights and Integration by Threshold Counting and Hashing). Etant donné l’accès à un oracle NP, pour une fonction booléenne F et une fonction de poids ρ données, WISH et SWITCH retournent une (ε,δ)-approximation du poids de F. J’exposerai les similarités des algorithmes en montrant notamment que leur fondements théoriques sont équivalents et qu’ils apportent des garanties similaires sur la qualité de l’approximation tout en ayant des complexités duales dans le sens où, à une permutation des paramètres près, la complexité de l’un correspond à celle de l’autre.