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. 

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)
  • Fellowships of Japan Society for Promotion of Science (2001, 2014) and Humboldt Fund (2002)
  • Symphosium of the Theory of computation (STOC), best paper award (2017).
  • Hood research fellowship, The UNiversity of Auckland (2015).


Deputy HOD Research

Selected publications and creative works (Research Outputs)

  • 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
  • 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
  • Gavryushkin, A., Khoussainov, B., & Stephan, F. (2016). Reducibilities among equivalence relations induced by recursively enumerable structures. Theoretical Computer Science, 612, 137-152. 10.1016/j.tcs.2015.11.042
  • Khoussainov, B. (2016). Quantifier Free Definability on Infinite Algebras. Paper presented at 31st Annual ACM-IEEE Symposium on Logic in Computer Science (LICS), New York City, NY. 5 July - 8 July 2016. PROCEEDINGS OF THE 31ST ANNUAL ACM-IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2016). (pp. 9). 10.1145/2933575.2934572
  • Berdinsky, D., & Khoussainov, B. (2016). Cayley Automatic Representations of Wreath Products. Int. J. Found. Comput. Sci, 27, 147-160. 10.1142/S0129054116400049
  • Jain, S., Khoussainov, B., & Stephan, F. (2016). Finitely Generated Semiautomatic Groups. Paper presented at 12th Conference on Computability in Europe (CiE), Paris, FRANCE. 27 June - 1 July 2016. Pursuit of the Universal. (pp. 10). 10.1007/978-3-319-40189-8_29

Contact details

Primary location

SCIENCE CENTRE 303 - Bldg 303
New Zealand

Web links