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