Khoussainov received his undergraduate degree from the Mathematics Department of Novosibirsk State University in 1984.
In 1991 Khoussainov joined Cornell University and held an H.C. Wang Assistant Professorship at the Mathematics Department from 1995 to 1997.
Khoussainov is a co-winner (together with Cristian Calude, Sanjay Jain, Wei Li and Frank Stephan) of the STOC 2017 best paper award[4] for a quasi-polynomial time algorithm deciding parity games.
For this work, Khoussainov and this paper's co-authors were awarded the 2021 EATCS-IPEC Nerode Prize.
[5] In 2023 while working in the UESTC, China, Khoussainov has also been elected as a foreign member of The Academia Europaea, the European Academy of Sciences, Humanities, Letters, and Law.