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.
Here is a list of research topics for students who would like to work on their Master or Doctoral degrees:
- Automatic structures
- Computable Model Theory
- Graph algorithms and complexity
- Games played on graphs and logic
- Topics in Model Checking, Specifications and Verfifications
- 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). Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 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