# Cristian S. Calude

Cristian Sorin Calude, né le 21 avril 1952 à Galați, est un mathématicien et informaticien, professeur à l'université d'Auckland. Il est connu en particulier pour ses recherches sur la complexité computationnelle et la théorie algorithmique de l'information. Il est l'initiateur de conférences internationales annuelles sur le calcul non conventionnel.

## Biographie

Après des études secondaires au collège Vasile Alecsandri à Galați, Cristian Calude s'inscrit en 1971 à l'université de Bucarest, où il suit en particulier les cours de Grigore Moisil et de Solomon Marcus$^,$. Il soutient en 1975, sous la direction de Marcus, une thèse intitulée « Categorical Methods in Computation Theory ».
Il enseigne et continue ses recherches à l'université de Bucarest, où il occupe plusieurs positions en mathématiques avant de devenir professeur à partir de 1994. Mais depuis 1992, il enseigne aussi au département d’informatique de l’université d’Auckland, en Nouvelle-Zélande, accédant à un poste de professeur en 1994. Il contribue à créer et dirige de 1995 à 2022 le Centre pour les mathématiques discrètes et l'informatique théorique de l'université d'Auckland.
Il est aussi chercheur associé ou consultant pour divers organismes et a été invité dans de nombreuses universités du monde entier, dont l'université libre de Bruxelles, l'université de Bourgogne, l'École normale supérieure et l'École polytechnique.

## Recherches

En 2017, avec Sanjay Jain, Bakhadyr Khoussainov, Wei Li et Frank Stephan, il a annoncé un algorithme pour décider des jeux de parité en temps quasi polynomial. Leur résultat a remporté un prix pour le meilleur article publié et le Prix EATCS-IPEC Nerode 2021.

## Publications (sélection)

* Experimental evidence of quantum randomness incomputability, avec M. J. Dinneen, Monica Dumitrescu, K. Svozil, "Physical Review A", 82, 022102 (2010), 1—8.
* Most programs stop quickly or never halt, avec M. A. Stay, "Advances in Applied Mathematics", 40 (2008), 295—308.
* Randomness & Complexity, From Leibniz to Chaitin, World Scientific, Singapore, 2007.
* Information and Randomness: An Algorithmic Perspective, 2nd Edition, Revised and Extended, Springer-Verlag, Berlin, 2002.
* Computing with Cells and Atoms, avec G. Păun ,Taylor & Francis Publishers, London, 2001.
* Theories of Computational Complexity, North-Holland, Amsterdam, 1988.

## Prix et distinctions

Calude a reçu de nombreux prix et distinctions au cours de sa carrière.
L'Académie roumaine lui a décerné le prix Gheorghe Lazar en 1988. Calude a été nommé au grade de chevalier de l'Ordre national du service fidèle de Roumanie) en juin 2019, « pour ses recherches, son activité pédagogique et son implication dans les échanges culturels entre la Roumanie et la Nouvelle-Zélande ».
Le 2 octobre 2023, l'Université Apollonia de Iași en Roumanie a accordé à Calude un doctorat honoris causa.
Calude a été Hood Fellow en 2008-2009 et il est membre de l'Academia Europaea depuis 2008.
Il a aussi obtenu (avec ses collaborateurs) un Computing Reviews Award, de l'Association for Computing Machinery, New York, États-Unis en 1986 et un STOC Best Paper Award en 2017, ainsi que le prix EATCS-IPEC Nerode en 2021.