# Cristian S. Calude

Cristian Sorin Calude (* 21. April 1952 in Galați, Rumänien) ist ein rumänisch-neuseeländischer Mathematiker und Informatiker.

## Leben

Er absolvierte das Gymnasium „Vasile Alecsandri“ in Galați und studierte an der Universität Bukarest. Er war Schüler von Grigore Moisil und Solomon Marcus, bei dem er 1977 an der Universität Bukarest promoviert wurde. Derzeit ist er ordentlicher Professor an der University of Auckland, Neuseeland, und auch der Gründungsdirektor des Zentrums für Diskrete Mathematik und Theoretische Informatik (CDMTCS) dort. Bis zum Jahre 2000 war er auch Professor an der Universität Bukarest.
Er war Gastprofessor an verschiedenen Universitäten in Europa, Nord- und Südamerika, Australien, Südafrika, unter anderem war er Monbusho Visiting Professor am Japan Advanced Institute of Science and Technology (JAIST) 1999, Gastprofessor an der ENS, Paris 2009, an der École polytechnique, Paris 2011, Visiting Fellow am Isaac Newton Institute for Mathematical Sciences, Cambridge 2012. Von 2017 bis 2020 ist er Gastprofessor an der Sun Yat-sen Universität in Guangdong, China.
Cristian Calude ist Autor oder Co-Autor von mehr als 250 wissenschaftlichen Artikeln und acht Büchern; diese Arbeiten wurden von mehr als 550 Autoren zitiert. Seine Arbeitsgebiete sind hauptsächlich Algorithmische Informationstheorie, Quanten-Computing, Diskrete Mathematik sowie Geschichte und Philosophie der Informatik. Im Jahre 2017 erzielte er gemeinsam mit Sanjay Jain, Bakhadyr Khoussainov, Wei Li, und Frank Stephan einen Algorithmus zur Entscheidung der Lösbarkeit von Paritätsspielen, welcher in quasipolynomieller Zeit arbeitet. Dieses Resultat wurde auf dem Symposium on Theory of Computing 2017 vorgestellt und gewann einen Best Paper Award.
Am 27. Juni 2019 wurde ihm durch den Präsidenten der Republik Rumänien Klaus Johannis der Treudienst-Orden der Klasse Ritter verliehen.
Gemeinsam mit Sanjay Jain, Bakhadyr Khoussainov, Wei Li, und Frank Stephan erhielt er im Jahre 2021 den EATCS Nerode Preis für den quasipolynomiellen Algorithmus zur Entscheidung der Lösbarkeit von Paritätsspielen.

## Ausgewählte Schriften

Artikel
* Cristian S. Calude, Karl Svozil: Binary Quantum Random Number Generator Based on Value Indefinite Observables. In: Nature, Scientific Reports. 2024, ISSN 2045-2322, doi:10.1038/s41598-024-62566-2 (englisch).
* José Manuel Agüero Trejo, Cristian S. Calude: Photonic ternary quantum random number generators. In: Proc. R. Soc. A. 2023, doi:10.1098/rspa.2022.0543 (englisch).
* Cristian S. Calude, Shahrokh Heidar, Joseph Sifakis: What perceptron neural networks are (not) good for? In: Information Sciences. 621. Jahrgang, 2023, S. 844–857, doi:10.1016/j.ins.2022.11.083 (englisch).
* C. S. Calude, S. Jain, B. Khoussainov, W. Li, F. Stephan: Deciding parity games in quasi-polynomial time. In: SIAM Journal on Computing. 2020, ISSN 0097-5397, S. STOC17–152—STOC17–188, doi:10.1137/17M1145288.
* Alastair A. Abbott, Cristian S. Calude, Michael J. Dinneen, Richard Hua: A hybrid quantum-classical paradigm to mitigate embedding costs in quantum annealing. In: International Journal of Quantum Information. 2019, ISSN 0219-7499, S. 1950042, doi:10.1142/S0219749919500424.
* Alastair A. Abbott, Cristian S. Calude, Michael J. Dinneen, Nan Huang: Experimentally probing the algorithmic randomness and incomputability of quantum randomness. In: Physica Scripta. Band 94, Nr. 4, 2019, ISSN 0031-8949, S. 045103, doi:10.1088/1402-4896/aaf36a.
* Cristian S. Calude, Monica Dumitrescu: A probabilistic anytime algorithm for the halting problem. In: Computability. Band 7, Nr. 2-3, 7. Juni 2018, ISSN 2211-3568, S. 259–271, doi:10.3233/COM-170073.
* Cristian S. Calude, Ludwig Staiger: Liouville, Computable, Borel Normal and Martin-Löf Random Numbers. In: Theory of Computing Systems. Band 62, Nr. 7, Oktober 2018, ISSN 1433-0490, S. 1573–1585, doi:10.1007/s00224-017-9767-8.
* Cristian S. Calude, Ludwig Staiger, Frank Stephan: Finite state incompressible infinite sequences. In: Information and Computation. Band 247, 2016, ISSN 0890-5401, S. 23–36, doi:10.1016/j.ic.2015.11.003.
* Cristian S. Calude, Giuseppe Longo: The Deluge of Spurious Correlations in Big Data. In: Foundations of Science. Band 22, Nr. 3, 2017, ISSN 1572-8471, S. 595–612, doi:10.1007/s10699-016-9489-4.
* Alastair A. Abbott, Cristian S. Calude, Karl Svozil: A variant of the Kochen-Specker theorem localising value indefiniteness. In: Journal of Mathematical Physics. Band 56, Nr. 10, 2015, ISSN 0022-2488, S. 102201, doi:10.1063/1.4931658.
* Cristian S. Calude, Elena Calude, Michael J. Dinneen: Guest Column: Adiabatic Quantum Computing Challenges. In: SIGACT News. Band 46, Nr. 1, 2015, ISSN 0163-5700, S. 40–61, doi:10.1145/2744447.2744459.
* Alastair A. Abbott, Cristian S. Calude, Karl Svozil: Value-indefinite observables are almost everywhere. In: Physical Review A. Band 89, Nr. 3, 2014, S. 032109–032116, doi:10.1103/PhysRevA.89.032109.
* Cristian S. Calude, Michael J. Dinneen, Monica Dumitrescu, Karl Svozil: Experimental evidence of quantum randomness incomputability. In: Physical Review A. Band 82, Nr. 2, August 2010, S. 022102, doi:10.1103/PhysRevA.82.022102.
* Cristian S. Calude, Michael A. Stay: Most programs stop quickly or never halt. In: Advances in Applied Mathematics. Band 40, Nr. 3, März 2008, ISSN 0196-8858, S. 295–308, doi:10.1016/j.aam.2007.01.001.
* Cristian S. Calude, Gregory J. Chaitin: Randomness everywhere. In: Nature. Band 400, Nr. 6742, 1999, S. 319–320, doi:10.1038/22435.
Bücher
* C. S. Calude. To Halt or Not to Halt? That Is the Question, World Scientific, Singapur, 2024. 10.1142/12159.
* A. Bellow, C. S. Calude, T. Zamfirescu (Hrsg.): Mathematics Almost Everywhere: In Memory of Solomon Marcus. World Scientific, Singapur 2018, doi:10.1142/10912.
* M. Burgin, C. S. Calude (Hrsg.): Information and Complexity. World Scientific, Singapur 2017 doi:10.1142/10017.
* C. S. Calude (Hrsg.): The Human Face of Computing. Imperial College Press, London 2015, doi:10.1142/p992.
* C. S. Calude (Hrsg.): Randomness & Complexity, From Leibniz to Chaitin. World Scientific, Singapur 2007.
* C. S. Calude: Information and Randomness: An Algorithmic Perspective. 2nd Edition, Revised and Extended, Springer-Verlag, Berlin 2002 (Leseprobe, books.google.com).
* C. S. Calude, G. Păun: Computing with Cells and Atoms. Taylor & Francis Publishers, London 2001 (Leseprobe, books.google.com).
* C. Calude: Theories of Computational Complexity. North-Holland, Amsterdam 1988 (Leseprobe, books.google.com).

## Auszeichnungen

* „Computing Reviews Award“, Association for Computing Machinery, New York, USA, 1986.
* „Gheorghe Lazar“ Mathematics Prize, Rumänische Akademie, Rumänien, 1988.
* Excellence in Research Award, Universität Bukarest, Rumänien, 2007.
* Dean’s Award for Excellence in Teaching, University of Auckland, 2007.
* Hood Fellow, 2008–2009.
* Mitglied der Academia Europaea, 2008.
* Ritter des Treudienst-Ordens der Republik Rumänien, Juni 2019.
* „EATCS-IPEC Nerode Preis“, 2021.
* "Mitlied SIGMA XI", 2024.