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., & 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
- 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
- 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, P. N., Behtenova, A., Popov, Z. I., Bakakin, V. V., Likhacheva, A. Y., Litasov, K. D., & Gavryushkin, A. (2016). Toward Analysis of Structural Changes Common for Alkaline Carbonates and Binary Compounds: Prediction of High-Pressure Structures of Li<inf>2</inf>CO<inf>3</inf>, Na<inf>2</inf>CO<inf>3</inf>, and K<inf>2</inf>CO<inf>3</inf>. Crystal Growth and Design, 16 (10), 5612-5617. 10.1021/acs.cgd.5b01793