Cristian S. Calude | |
|---|---|
 Calude in 2011 | |
| Born | 21 April 1952 |
| Nationality | Romanian |
| Alma mater | University of Bucharest |
| Known for | Algorithmic Information Theory and Quantum Theory contributions |
| Scientific career | |
| Fields | Mathematician |
| Institutions | University of Auckland, Academia Europaea |
| Thesis | 1977 |
| Doctoral advisor | Solomon Marcus |
| Website | calude |
Cristian Sorin Calude (born 21 April 1952) is a Romanian-New Zealander mathematician and computer scientist. [1]
After graduating from the Vasile Alecsandri National College in Galați, he studied at the University of Bucharest, where he was student of Grigore C. Moisil and Solomon Marcus. [2] Calude received his Ph.D. in Mathematics from the University of Bucharest under the direction of Solomon Marcus in 1977. [3]
He is currently chair professor at the University of Auckland, [4] New Zealand and also the founding director of the Centre for Discrete Mathematics and Theoretical Computer Science. [5] Visiting professor in many universities in Europe, North and South America, Australasia, South Africa, including Monbusho Visiting professor, JAIST, 1999 and visiting professor ENS, Paris, 2009, École Polytechnique, Paris, 2011; visiting fellow, Isaac Newton Institute for Mathematical Sciences, 2012; guest professor, Sun Yat-sen University, Guangzhou, China, 2017–2020; visiting fellow ETH Zurich, 2019. Former professor at the University of Bucharest. Calude is author or co-author of more than 270 research articles and 8 books, [6] and is cited by more than 550 authors. [7] He is known for research in algorithmic information theory, quantum computing, discrete mathematics and the history and philosophy of computation. [8]
In 2017, together with Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan, he announced an algorithm for deciding parity games in quasipolynomial time. [9] Their result was presented by Bakhadyr Khoussainov at the Symposium on Theory of Computing 2017 [10] and won a Best Paper Award. [11]
Calude was awarded the National Order of Faithful Service in the degree of Knight [12] by the President of Romania, Mr. Klaus Iohannis, in June 2019.
In 2021, together with Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan, he won the EATCS Nerode Prize [13] for their quasipolynomial time algorithm for deciding parity games.
| International | |
|---|---|
| National | |
| Academics | |
| Other | |
In the computer science subfield of algorithmic information theory, a Chaitin constant or halting probability is a real number that, informally speaking, represents the probability that a randomly constructed program will halt. These numbers are formed from a construction due to Gregory Chaitin.
Gregory John Chaitin is an Argentine-American mathematician and computer scientist. Beginning in the late 1960s, Chaitin made contributions to algorithmic information theory and metamathematics, in particular a computer-theoretic result equivalent to Gödel's incompleteness theorem. He is considered to be one of the founders of what is today known as algorithmic complexity together with Andrei Kolmogorov and Ray Solomonoff. Along with the works of e.g. Solomonoff, Kolmogorov, Martin-Löf, and Leonid Levin, algorithmic information theory became a foundational part of theoretical computer science, information theory, and mathematical logic. It is a common subject in several computer science curricula. Besides computer scientists, Chaitin's work draws attention of many philosophers and mathematicians to fundamental problems in mathematical creativity and digital philosophy.
A quantum computer is a computer that takes advantage of quantum mechanical phenomena.
Peter Williston Shor is an American professor of applied mathematics at MIT. He is known for his work on quantum computation, in particular for devising Shor's algorithm, a quantum algorithm for factoring exponentially faster than the best currently-known algorithm running on a classical computer.
Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, formal language theory, the lambda calculus and type theory.
In theoretical computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by the algorithm, supposing that each elementary operation takes a fixed amount of time to perform. Thus, the amount of time taken and the number of elementary operations performed by the algorithm are taken to be related by a constant factor.
Solomon Marcus was a Romanian mathematician, member of the Mathematical Section of the Romanian Academy and emeritus professor of the University of Bucharest's Faculty of Mathematics.
Algorithmic information theory (AIT) is a branch of theoretical computer science that concerns itself with the relationship between computation and information of computably generated objects (as opposed to stochastically generated), such as strings or any other data structure. In other words, it is shown within algorithmic information theory that computational incompressibility "mimics" (except for a constant that only depends on the chosen universal programming language) the relations or inequalities found in information theory. According to Gregory Chaitin, it is "the result of putting Shannon's information theory and Turing's computability theory into a cocktail shaker and shaking vigorously."
László "Laci" Babai is a Hungarian professor of computer science and mathematics at the University of Chicago. His research focuses on computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields.
Michael J. Dinneen is an American-New Zealand mathematician and computer scientist working as a senior lecturer at the University of Auckland, New Zealand. He is co-director of the Center for Discrete Mathematics and Theoretical Computer Science. He does research in combinatorial algorithms, distributive programming, experimental graph theory, and experimental algorithmic information theory.
A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a token along the edges of the graph. The owner of the node that the token falls on selects the successor node. The players keep moving the token, resulting in a path, called a play.
In common usage, randomness is the apparent or actual lack of definite pattern or predictability in information. A random sequence of events, symbols or steps often has no order and does not follow an intelligible pattern or combination. Individual random events are, by definition, unpredictable, but if the probability distribution is known, the frequency of different outcomes over repeated events is predictable. For example, when throwing two dice, the outcome of any particular roll is unpredictable, but a sum of 7 will tend to occur twice as often as 4. In this view, randomness is not haphazardness; it is a measure of uncertainty of an outcome. Randomness applies to concepts of chance, probability, and information entropy.
In computational complexity theory and the analysis of algorithms, an algorithm is said to take quasi-polynomial time if its time complexity is quasi-polynomially bounded. That is, there should exist a constant such that the worst-case running time of the algorithm, on inputs of size , has an upper bound of the form
Lance Jeremy Fortnow is a computer scientist known for major results in computational complexity and interactive proof systems. He is currently Dean of the College of Computing at the Illinois Institute of Technology.
Karl Svozil is an Austrian physicist educated at the University of Vienna and Heidelberg University. Visiting scholar at the Lawrence Berkeley Laboratory of the University of California at Berkeley, US (1982–1983), the Lebedev Institute of the Moscow State University, and the Ioffe Institute, St. Petersburg (1986). Docent in Theoretical Physics at the Vienna Technical University. Ao. Univ. Professor at the Institute for Theoretical Physics of the Vienna Technical University. External Researcher at the Centre for Discrete Mathematics and Theoretical Computer Science of the University of Auckland.
The EATCS–IPEC Nerode Prize is a theoretical computer science prize awarded for outstanding research in the area of multivariate algorithmics. It is awarded by the European Association for Theoretical Computer Science and the International Symposium on Parameterized and Exact Computation. The prize was offered for the first time in 2013.
Ludwig Staiger is a German mathematician and computer scientist at the Martin Luther University of Halle-Wittenberg.
Universality probability is an abstruse probability measure in computational complexity theory that concerns universal Turing machines.
Continuous-variable (CV) quantum information is the area of quantum information science that makes use of physical observables, like the strength of an electromagnetic field, whose numerical values belong to continuous intervals. One primary application is quantum computing. In a sense, continuous-variable quantum computation is "analog", while quantum computation using qubits is "digital." In more technical terms, the former makes use of Hilbert spaces that are infinite-dimensional, while the Hilbert spaces for systems comprising collections of qubits are finite-dimensional. One motivation for studying continuous-variable quantum computation is to understand what resources are necessary to make quantum computers more powerful than classical ones.
Bakhadyr M. Khoussainov is a computer scientist and mathematician, who was born and educated in the Soviet Union, works in the fields of mathematical logic, computability theory, computable model theory and theoretical computer science. With Anil Nerode, he is the co-founder of the theory of automatic structures, which is an extension of the theory of automatic groups.