Cristian 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 Zealand 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 | |
| People | |
| 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 exploits quantum mechanical phenomena. On small scales, physical matter exhibits properties of both particles and waves, and quantum computing leverages this behavior using specialized hardware. Classical physics cannot explain the operation of these quantum devices, and a scalable quantum computer could perform some calculations exponentially faster than any modern "classical" computer. Theoretically a large-scale quantum computer could break some widely used encryption schemes and aid physicists in performing physical simulations; however, the current state of the art is largely experimental and impractical, with several obstacles to useful applications.
Hypercomputation or super-Turing computation is a set of hypothetical models of computation that can provide outputs that are not Turing-computable. For example, a machine that could solve the halting problem would be a hypercomputer; so too would one that could correctly evaluate every statement in Peano arithmetic.
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.
In quantum computing, a quantum algorithm is an algorithm that runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical algorithm is a finite sequence of instructions, or a step-by-step procedure for solving a problem, where each step or instruction can be performed on a classical computer. Similarly, a quantum algorithm is a step-by-step procedure, where each of the steps can be performed on a quantum computer. Although all classical algorithms can also be performed on a quantum computer, the term quantum algorithm is generally reserved for algorithms that seem inherently quantum, or use some essential feature of quantum computation such as quantum superposition or quantum entanglement.
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.
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.
Quantum neural networks are computational neural network models which are based on the principles of quantum mechanics. The first ideas on quantum neural computation were published independently in 1995 by Subhash Kak and Ron Chrisley, engaging with the theory of quantum mind, which posits that quantum effects play a role in cognitive function. However, typical research in quantum neural networks involves combining classical artificial neural network models with the advantages of quantum information in order to develop more efficient algorithms. One important motivation for these investigations is the difficulty to train classical neural networks, especially in big data applications. The hope is that features of quantum computing such as quantum parallelism or the effects of interference and entanglement can be used as resources. Since the technological implementation of a quantum computer is still in a premature stage, such quantum neural network models are mostly theoretical proposals that await their full implementation in physical experiments.
In computational complexity, problems that are in the complexity class NP but are neither in the class P nor NP-complete are called NP-intermediate, and the class of such problems is called NPI. Ladner's theorem, shown in 1975 by Richard E. Ladner, is a result asserting that, if P ≠ NP, then NPI is not empty; that is, NP contains problems that are neither in P nor NP-complete. Since it is also true that if NPI problems exist, then P ≠ NP, it follows that P = NP if and only if NPI is empty.
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 deputy director of the Center for Discrete Mathematics and Theoretical Computer Science. He does research in combinatorial optimization, distributed computing, and graph theory.
Quantum walks are quantum analogs of classical random walks. In contrast to the classical random walk, where the walker occupies definite states and the randomness arises due to stochastic transitions between states, in quantum walks randomness arises through (1) quantum superposition of states, (2) non-random, reversible unitary evolution and (3) collapse of the wave function due to state measurements. Quantum walks are a technique for building quantum algorithms.
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
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.
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.
Oded Regev is an Israeli-American theoretical computer scientist and mathematician. He is a professor of computer science at the Courant institute at New York University. He is best known for his work in lattice-based cryptography, and in particular for introducing the learning with errors problem.
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.
This glossary of quantum computing is a list of definitions of terms and concepts used in quantum computing, its sub-disciplines, and related fields.