Theory Group

About us

We study theoretical computer science, the branch of computer science that focuses on the abstract, mathematical nature of computation.

Our main interests lie in the general areas of automata theory, computational biology, computational complexity, computability and randomness, design and analysis of algorithms, unconventional models of computation. We are also interested in related areas, such as biology, combinatorics, logic, and theoretical physics.

Members also belong to the Centre for Discrete Mathematics and Theoretical Computer Science (CDMTCS), and we contribute to the CDMTCS report series. We have seminars throughout the year and visitors are welcome.

People

Staff - principal members

Cristian S. Calude (professor) works in algorithmic information theory (theory and applications to logic and computation) and unconventional computing (quantum computing and physics of computation). Cris's publications.

Michael J. Dinneen (senior lecturer) works in the field of combinatorial algorithms, graph theory and network design. Interests in distributive programming, computational complexity, programming trends, computational biology and computer-assisted mathematics. He is actively involved in both the NZ and ACM programming contests and has coached several teams at the world finals. Michael's publications.

Alexei Drummond (associate professor) is interested in evolutionary bioinformatics. His focus in on the use of Markov chain Monte Carlo to perform Bayesian inference of probablistic models of molecular evolution and coalescent-based models of population genetics. His methods have been applied to understanding the evolution of viruses, genomes and languages. Alexei's publications.

Bakhadyr Khoussainov (professor) is interested in logic and computability with an emphasis on automata theory and its applications, computable algebra and model theory, games on graphs and graph algorithms, Kolmogorov complexity, and algebraic specifications of abstract data types. Bakh's publications.

Sabastian Link (associate professor) is interestsed in XML constraints, complex-value databases, data dependencies and conceptual modelling. Sabastian's publications.

Andre Nies (associate professor) works in (1) Computability theory and (2) algebra and automatic structures. (1) In earlier papers he has investigated degree structures using model theoretic methods. In recent years he has studied the interplay of computability and randomness. (2) He applies logical methods especially to groups, and studies which structures can be described by automata. Andre's publications.

Jing Sun (senior lecturer) interests in formal engineering methods, semantic web, formal specification, validation and verification, model checking, theorem proving and ontology reasoning. Jing's publications.

David Welch (lecturer) interests in Bayesian computational methods, including MCMC and ABC statistical models and inference for epidemiology, epidemics on networks, and inference for coalescent-based population genetics. David's publications.

Mark C. Wilson (senior lecturer) studies combinatorics, algorithms, discrete probability, and their interactions. Particular topics of recent interest are: theory and applications of generating functions; probabilistic analysis of algorithms; social choice theory. Mark's publications.

Associate members

G. J. Chaitin (honorary visiting professor) works in algorithmic information theory and digital philosophy. Greg's publications. LISP interpreter for The Limits of Mathematics, The Unknowable, Exploring Randomness.

Gill Dobbie (associate professor) studies databases, the web, and software engineering. Particular interests include the foundations of database systems, defining logical models for various kinds of database systems, and reasoning about the correctness of algorithms in that setting.

Radu Nicolescu (senior lecturer) . Radu's publications.

Alexander Raichev (postdoctoral research fellow) works in combinatorics, studying the asymptotics of coefficients of multivariate generating functions. One application of this research is to the analysis of algorithms. He is also interested in mathematical logic, computability theory, and Kolmogorov complexity. Alex's publications.

Gerald Weber (lecturer) studies software architecture, software engineering, computer supported cooperative work (CSCW) web services and the semantic web and computational Geometry, theory of computation.

Postgraduate Students

Hector Zenil (PhD student). Experimental AIT with Cris Calude and Jean-Paul Delahaye.
Michael John Brough (MSc student). Automatic algebras with Bakh Khoussainov.
Nicolas Derian (MSc student). Evolutionary mode and tempo of Hepatitis C virus with Alexei Drummond.
Nick Hay (PhD student). Algorithmic probability and inductive inference with Cristian S. Calude and Mike Barley.
Joseph Heled (PhD student). Modeling the interface between population genetics and phylogenetics with Alexei Drummond.
Yun-Bum Kim (PhD student). Synchronization in membrane computing (P systems) with Radu Nicolescu and Michael J. Dinneen.
Sibon Li (PhD student). A comparative genomic approach to detecting lineage specific selection in genome non-coding regions with Alexei Drummond.
Jiamou Liu (PhD student). Automatic structures with Bakhadyr Khoussainov.
Sidney Markowitz (PhD student). Simulation models of prebiotic evolution of genetic coding with Alexei Drummond.
Alexander Melnikov (PhD students). Randomness with Bakhadyr Khoussainov and Andre Nies.
Reyhaneh Reyhani (PhD student). Computational social choice theory with Mark Wilson.
Alastair Abbott (PhD student). Algorithmic information theory and randomness in quantum mechanics with Cristian S. Calude (UoA) and Giuseppe Longo (Ecole Polytechnique).
Ralph Versteegen (MSc student). Graph partial orders and forbidden minors with Michael Dinneen and Marston Conder.
Andrew Probert (MSc student). Parameterized complexity techniques and GPGPU programming with Michael Dinneen.
Kuai Wei (PhD student). Parallel and Memetic Algorithms with Michael Dinneen.
Edwin Flores (MSc student, part-time). Graph optimization problems with Michael Dinneen.
Tania K. Roblot (PhD student). AIT and finite computable complexity measures with Cristian S. Calude and Bakhadyr Khoussainov.

News and Events

An International Workshop on Theoretical Computer Science Dedicated to Prof. Cristian S. Calude's 60th Birthday took place in February 2012 in Auckland, New Zealand. A volume titled "Computation, Physics and Beyond", based on the WTCS2012, was published in the LNCS Festschrifts Series of Springer.
Arkadii Slinko and Mark Wilson establish the Centre for Mathemataical Social Science in 2009.
The Fourth International Conference on Combinatorial Mathematics and Combinatorial Computing (4ICC) was held here in December 2008, organized by Mark Wilson with help from Alex Raichev, Michael Dinneen, Masoud Khosravani and Reyhaneh Reyhani.
In early 2008 an NZIMA programme Algorithms: New Directions and Applications will run. Mark Wilson is associate director and Michael Dinneen on the programme committee. Substantial activity including public lectures will occur at the University of Auckland.
University of Auckland Team (Andrew Olsen, Robert Bowmaker and Stephen Merriman, trained by Dr. Michael Dinneen, pictured here) finished 11th from 88 in the 31st ACM International Collegiate Programming Contest World Finals (March 12-16, 2007 Hilton Tokyo Bay Hotel) and won a Bronze Medal.

Courses

We are involved in a variety of courses at undergraduate level, mostly those with a strong ``theory" component. At graduate level, we offer several courses. More details to come.

UoA CS Theory Group