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 contraintesConstraint 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]
↑Dmitriy Zhuk, « A Proof of the CSP Dichotomy Conjecture », 58th Annual Symposium on Foundations of Computer Science (FOCS), IEEE, , p. 319–330 (DOI10.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 (DOI10.1109/FOCS.2017.37).
↑Dmitriy Zhuk, « A Proof of the CSP Dichotomy Conjecture », Journal of the ACM, vol. 67, no 5, , article no 30 (ISSN0004-5411, DOI10.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, (arXiv2104.11808).
