Professor Bakh Khoussainov

Profile Image
Professor (Personal Chair)


I have a PhD (1988) from Algebra and Logic Department, Novosibirsk University, Russia. I have been in the Computer Science Department in the University of Auckland since 1996.

I held H.C.Wang Assistant Professorship at Cornell University and have had visiting positions at the University of Chicago, University of Wisconsin-Madison, Cornell University (all USA), Japan Advanced Institute of Science and Techology, Heidelberg University (Germany), National University of Singapore, Kyoto University. 

I have presented about 200 lectures and invited talks at international conferences and seminars. I have also been awarded Marsden Fund research grants for the periods 2001-2003, 2004-2006, 2007-2011, and 2011-2016. I am also a Fellow of Royal Society of New Zealand since 2005, Humboldt Fellow in 2002, JSPS Fellow (2000, 2013, 2015),  and Aitken Lecturer 2019. 

Research | Current

My research interests are in algorithms, computability, automata, logic, and applications.

Postgraduate supervision

Here is a list of research topics for students who would like to work on their Master or Doctoral degrees:

  1. Automatic structures
  2. Computable Model Theory
  3. Graph algorithms and complexity
  4. Games played on graphs and logic
  5. Topics in Model Checking, Specifications and Verfifications
  6. Randomness and Computability

With my support, all my PhD students during their study spend several semesters at the mathematics and computer science departments of Cornell University; this gives them the edge as they learn from the best, and take really cool graduate classes in mathematics and computer science. I have supervised 12 PhD students.


  • New Zealand Mathematical Society Research Award (2002).
  • University of Auckland Distinguished Teaching Award (2001).
  • Invitation Fellowships of Japan Society for Promotion of Science (2001, 2013, and 2015).
  • Humboldt Fund (2002)
  • Symphosium of the Theory of computation (STOC), best paper award (2017).
  • Hood research fellowship, The University of Auckland (2015).
  • 2019 Aitken Lecturer (selected by both the London Math Society and New Zealand Math Society).


Deputy HoD Research (2002-2009, 2010-2011).

Deputy HOD Academic (2013-2015)

A Member of the FSC (2017-Present)

Areas of expertise

Logic, Computability, Automata, Formal Languages, Complexity

Selected publications and creative works (Research Outputs)

  • Khoussainov, B., & Takisaka, T. (2017). Large scale geometries of infinite strings. Proceedings - Symposium on Logic in Computer Science. 10.1109/LICS.2017.8005078
  • Calude, C. S., Jain, S., Khoussainov, B., Li, W., & Stephan, F. (2017). Deciding parity games in quasipolynomial time. STOC 2017 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, Part F128415, 252-263. New York, NY, USA: ACM. 10.1145/3055399.3055409
    Other University of Auckland co-authors: Cristian Calude
  • Bhatti, Z. E. (2017). Model-Based Safety Assessment of Industrial Automation Systems using IEC 61499 The University of Auckland. ResearchSpace@Auckland.
    Other University of Auckland co-authors: Partha Roop
  • Gavryushkin, A., Khoussainov, B., Kokho, M., & Liu, J. (2016). Dynamic algorithms for multimachine interval scheduling through analysis of idle intervals. Algorithmica, 76 (4), 1160-1180. 10.1007/s00453-016-0148-5
    Other University of Auckland co-authors: Jiamou Liu
  • Gavryushkin, A., & Drummond, A. J. (2016). The space of ultrametric phylogenetic trees. Journal of theoretical biology, 403, 197-208. 10.1016/j.jtbi.2016.05.001
    Other University of Auckland co-authors: Alexei Drummond
  • FOKINA, E. K. A. T. E. R. I. N. A., KHOUSSAINOV, B. A. K. H. A. D. Y. R., SEMUKHIN, P. A. V. E. L., & TURETSKY, D. A. N. I. E. L. (2016). LINEAR ORDERS REALIZED BY C.E. EQUIVALENCE RELATIONS. The Journal of Symbolic Logic, 81 (02), 463-482. 10.1017/jsl.2015.11
  • Jain, S., Khoussainov, B., Schlicht, P., & Stephan, F. (2016). Tree-automatic scattered linear orders. Theoretical Computer Science, 626, 83-96. 10.1016/j.tcs.2016.02.008
  • Berdinsky, D., & Khoussainov, B. (2016). Cayley Automatic Representations of Wreath Products. International Journal of Foundations of Computer Science, 27 (02), 147-159. 10.1142/S0129054116400049

Contact details

Primary office location

SCIENCE CENTRE 303 - Bldg 303
New Zealand

Web links