Dmitriy Zhuk
Dimitri Zhuk (en russe : Дмитрий Николаевич Жук) est un informaticien théoricien russe, né le 25 août 1984 à Tcherepovets. Zhuk est lauréat, en 2021, du prix Presburger[1].
Carrière
En 2001, Zhuk obtient son diplôme de l'école d'État de Vologda pour les sciences mathématiques et naturelles (VGEML) et est admis comme étudiant au département de mathématiques de l'université d'État de Moscou. Il étudie sous la supervision du professeur V. B. Kudryavtsev. Dans sa thèse, Dmitriy décrit complètement toutes les classes (maximales) précomplètes dans une classe importante de fonctions hétérogènes.
En 2006, Dmitriy Zhuk obtenu son diplôme avec distinction au département de mathématiques et poursuitses recherche dans le sous-département de théorie mathématique des systèmes intelligents, où il effectue des recherches en théorie des automates. Dans sa thèse de doctorat, Dmitriy Zhuk décrit la frontière précise entre les cas algorithmiquement insolubles et les cas algorithmiquement décidables pour le problème de la A-complétude.
Depuis octobre 2009, Dmitriy occupe un poste de chercheur junior au sein du sous-département de théorie mathématique des systèmes intelligents et travaille principalement sur la théorie des clones[2].
Travaux
Dmitriy Zhuk a présenté en 2017 une solution à la conjecture de la dichotomie du problème de satisfaction de contraintes Constraint Satisfaction Problem (CSP)[3]. La conjecture de dichotomie pour le CSP non uniforme stipule que pour tout langage de contraintes Γ, le problème CSP(Γ) est soit soluble en temps polynomial, soit NP-complet. La conjecture a été proposée par Feder et Vardi dans leur article fondateur de 1993[4]. Une preuve différente de la conjecture a été publiée simultanément et indépendamment par Andrei Bulatov[5]. La preuve de Zhuk (comme celle de Bulatov) repose sur une approche algébrique et sur la connexion entre l'algèbre universelle et CSP, connexion qui a été établie à la fin des années 90. L'algorithme de Zhuk pour résoudre la conjecture algébrique est une combinaison ingénieuse de vérification de cohérence, de récursion et de procédures d'apprentissage pour les espaces affines, et apporte des techniques nouvelles qui ont déjà et auront d'autres applications dans le domaine des CSP et au-delà[1]. La preuve de Zhuk est parue en revue en 2020[6]. Une approche unificatrice a été proposée en 2021 par Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik et Dmitriy Zhuk[7]
Notes et références
- Laudatio Dmitriy Zhuk sur EATCS
- Dimitri Zhuk sur intsys.msu.ru/en/.
- Dmitriy Zhuk, « A Proof of the CSP Dichotomy Conjecture », 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, , p. 319–330 (DOI 10.1109/FOCS.2017.38)
- Tomas Feder et Moshe Y. Vardi, « Monotone Monadic SNP and Constraint Satisfaction », STOC, , p. 612-622.
- Andrei A. Bulatov, « A Dichotomy Theorem for Nonuniform CSPs », 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, , p. 319–330 (DOI 10.1109/FOCS.2017.37).
- Dmitriy Zhuk, « A Proof of the CSP Dichotomy Conjecture », Journal of the ACM, vol. 67, no 5, , article no 30 (ISSN 0004-5411, DOI 10.1145/3402029)
- Libor Barto, Zarathustra Brady, Andrei Bulatov, Marcin Kozik et Dmitriy Zhuk, « Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP », prépublication, (arXiv 2104.11808).
Liens externes
- Page personnelle de Dmitriy Zhuk] sur Intelligent Systems.
- Publications de Dmitriy Zhuk sur DBLP.