Professor Bakh Khoussainov


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)

  • Jain, S., Khoussainov, B., Schlicht, P., & Stephan, F. (2019). The isomorphism problem for tree-automatic ordinals with addition. INFORMATION PROCESSING LETTERS, 149, 19-24. 10.1016/j.ipl.2019.05.004
  • Jain, S., Khoussainov, B., & Stephan, F. (2018). Finitely generated semiautomatic groups. Computability, 7 (2-3), 273-287. 10.3233/COM-180089
  • Khoussainov, B. (2018). A Brief Excursion to Parity Games. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 10.1007/978-3-319-98654-8_3
  • Khoussainov, B. (2018). A Journey to Computably Enumerable Structures (Tutorial Lectures). Paper presented at 14th Conference on Computability in Europe (CiE), Kiel, GERMANY. 30 July - 3 August 2018. SAILING ROUTES IN THE WORLD OF COMPUTATION. (pp. 19). 10.1007/978-3-319-94418-0_1
  • Jain, S., Khoussainov, B., Stephan, F., Teng, D., & Zou, S. (2017). Semiautomatic structures. Theory of Computing Systems, 61 (4), 1254-1287. 10.1007/s00224-017-9792-7
  • Khoussainov, B., & Takisaka, T. (2017). Large scale geometries of infinite strings. Paper presented at LICS 2017. Proceedings - Symposium on Logic in Computer Science. 10.1109/LICS.2017.8005078
  • (2017). Computability and Complexity - Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday. Computability and Complexity.
  • 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

Contact details

Primary office location

SCIENCE CENTRE 303 - Bldg 303
Level 4, Room 405
New Zealand

Web links