## 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 (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. |

Tanya Gvozdeva graduated from Novosibirsk State University in 2006, with honours. She did a MSc thesis on hyperbolic geometry under the supervision of Prof. Mednyh. In 2008 she came to the University of Auckland as a PhD student under the supervision of Prof. Slinko. She defended her thesis ``Simple Games: Weightedness and Generalizations'' in 2012. Tanya has worked as a postdoc and a lecturer in NTU (Singapore), Victoria (Wellington), and Massey (Auckland). |

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. |

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

Simone Linz (lecturer) is interestsed in mathematical and computational biology; in particular algorithmic and combinatorial problems arising in phylogenetics (evolutionary biology). Simone's publications. |

Andre Nies (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. |

David Welch (senior 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 (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) Discrete mathematical models; Information coding and complexity; Service oriented computing; Integrating objects, XML and databases. 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 (senior 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.
- 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.## Links

- Slideshow on theoretical computer science for Stage 1 students, by Mark Wilson
- Centre for Discrete Mathematics and Theoretical Computer Science (CDMTCS)
- Theory Matters Wiki, a good place for publicity and information about TCS
- Contributions of theoretical computer science, a report from ACM SIGACT
- ACM Special Interest Group on Algorithms and Computation Theory (SIGACT)
- European Association for Theoretical Computer Science (EATCS)