Chercheur postdoctoral en complexité de la preuve et compilation de connaissances h/f

Recherche sur les systèmes de preuves pour des problèmes plus complexes que SAT, donc situé dans des classes de complexité au-delà de NP.
Activités
La personne recrutée travaillera sur la conception et le développement de système de preuves pour la compilation de connaissances et le comptage de modèle sur différents semi-anneaux, dans le cadre du projet de CPJ "TruKC : Trusted Knowledge Compilers" et que l'on peut voir comme une extension des idées présentées dans [1]. Une partie des travaux sera de nature théorique avec l'élaboration de nouveaux systèmes de preuves, l'étude des forces respectives des différents sytèmes de preuves existants en prouvant à la fois des bornes inférieures et des bornes supérieures sur les tailles de celle-ci. Les travaux pourront être complémentés par des développements pratiques comme la certification d'outils provenant de la compilation de connaissances.

[1] Capelli, Florent. "Knowledge compilation languages as proof systems." Theory and Applications of Satisfiability Testing-SAT 2019 : 22nd International Conference, SAT 2019, Lisbon, Portugal, July 9-12, 2019, Proceedings 22. Springer International Publishing, 2019.

Compétences
Formation solide en informatique théorique. Connaissances dans au moins un des domaines suivants souhaitées :
- Complexité de la preuve
- Compilation de connaissances,
- Complexité de comptage
- Complexité paramétrée.
Contexte de travail


L'activité sera effectuée au sein du Centre de Recherche en Informatique de Lens. Le CRIL est un laboratoire situé à Lens, spécialisé dans différents aspects de l'intelligence artificielle.