Bakhadyr M. Khoussainov (

Cyrillic , bg, кирилица , mk, кирилица , russian: кириллица , sr, ћирилица, uk, кирилиця , fam1 = Egyptian hieroglyphs , fam2 = Proto-Sinaitic , fam3 = Phoenician , fam4 = G ...

: Бахадыр Хусаинов) is a

computer scientist A computer scientist is a person who is trained in the academic study of computer science. Computer scientists typically work on the theoretical side of computation, as opposed to the hardware side on which computer engineers mainly focus (al ...

and

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, structure, space, models, and change. History On ...

, who was born and educated in the

Soviet Union The Soviet Union,. officially the Union of Soviet Socialist Republics. (USSR),. was a transcontinental country that spanned much of Eurasia from 1922 to 1991. A flagship communist state, it was nominally a federal union of fifteen national ...

, works in the fields of

mathematical logic Mathematical logic is the study of logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory. Research in mathematical logic commonly addresses the mathematical properties of for ...

computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since e ...

, computable model theory and

theoretical computer science Theoretical computer science (TCS) is a subset of general computer science and mathematics that focuses on mathematical aspects of computer science such as the theory of computation, lambda calculus, and type theory. It is difficult to circumsc ...

. With

Anil Nerode Anil Nerode (born 1932) is an American mathematician. He received his undergraduate education and a Ph.D. in mathematics from the University of Chicago, the latter under the directions of Saunders Mac Lane. He enrolled in the Hutchins College at t ...

, he is the co-founder of the theory of automatic structures, which is an extension of the theory of

automatic group In mathematics, an automatic group is a finitely generated group equipped with several finite-state automata. These automata represent the Cayley graph of the group. That is, they can tell if a given word representation of a group element is in a ...

Biography

Khoussainov received his undergraduate degree from the Mathematics Department of

Novosibirsk State University Novosibirsk State University is a public research university located in Novosibirsk, Russia. The university was founded in 1958, on the principles of integration of education and science, early involvement of students with research activities an ...

in 1984. In 1988, he received his

Candidate of Sciences Candidate of Sciences (russian: кандидат наук, translit=kandidat nauk) is the first of two doctoral level scientific degrees in Russia and the Commonwealth of Independent States. It is formally classified as UNESCO's ISCED level 8, "do ...

degree (equivalent to a PhD) in Algebra and Logic from

with the supervision of an Academician of the

Russian Academy of Sciences The Russian Academy of Sciences (RAS; russian: Росси́йская акаде́мия нау́к (РАН) ''Rossíyskaya akadémiya naúk'') consists of the national academy of Russia; a network of scientific research institutes from across t ...

. In 1991 Khoussainov joined

Cornell University Cornell University is a private statutory land-grant research university based in Ithaca, New York. It is a member of the Ivy League. Founded in 1865 by Ezra Cornell and Andrew Dickson White, Cornell was founded with the intention to teach an ...

and held an Ｈ.C. Wang Assistant Professorship at the Mathematics Department from 1995 to 1997. In 1996 Khoussainov joined the

University of Auckland , mottoeng = By natural ability and hard work , established = 1883; years ago , endowment = NZD $293 million (31 December 2021) , budget = NZD $1.281 billion (31 December 2021) , chancellor = Cecilia Tarrant , vice_chancellor = Dawn F ...

, and remained until 2021 when he moved to the

UESTC The University of Electronic Science and Technology of China (UESTC) is a national public research university in Chengdu, Sichuan, China. It was founded in 1956 instructed by the Premier Zhou Enlai. UESTC was established on the basis of the incorp ...

. Khoussainov has held visiting positions at

, the

University of Chicago The University of Chicago (UChicago, Chicago, U of C, or UChi) is a private research university in Chicago, Illinois. Its main campus is located in Chicago's Hyde Park neighborhood. The University of Chicago is consistently ranked among the b ...

, the

National University of Singapore The National University of Singapore (NUS) is a national public research university in Singapore. Founded in 1905 as the Straits Settlements and Federated Malay States Government Medical School, NUS is the oldest autonomous university in the c ...

Kyoto University , mottoeng = Freedom of academic culture , established = , type = National university, Public (National) , endowment = ¥ 316 billion (2.4 1000000000 (number), billion USD) , faculty = 3,480 (Teaching Staff) , administrative_staff ...

JAIST is a postgraduate university in Japan, established in 1990. JAIST was established in the centre of Ishikawa Science Park (ISP). It is to the south of Kanazawa City. JAIST has programs of advanced research and development in science and technol ...

and the

University of Wisconsin-Madison A university () is an institution of higher (or tertiary) education and research which awards academic degrees in several academic disciplines. Universities typically offer both undergraduate and postgraduate programs. In the United States, the ...

Awards and recognition

Khoussainov is a co-winner (together with Cristian Calude, Sanjay Jain, Wei Li and Frank Stephan) of the STOC 2017 best paper award for a

quasi-polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

algorithm deciding

parity game A parity game is played on a colored directed graph, where each node has been colored by a priority – one of (usually) finitely many natural numbers. Two players, 0 and 1, move a (single, shared) token along the edges of the graph. The owne ...

s. For this work, Khoussainov and this paper's co-authors were awarded the 2021 EATCS-IPEC

Nerode Prize The EATCS–IPEC Nerode Prize is a theoretical computer science prize awarded for outstanding research in the area of multivariate algorithmics. It is awarded by the European Association for Theoretical Computer Science and the International Sym ...

. A fellow of the

Royal Society of New Zealand Royal may refer to: People * Royal (name), a list of people with either the surname or given name * A member of a royal family Places United States * Royal, Arkansas, an unincorporated community * Royal, Illinois, a village * Royal, Iowa, a cit ...

, Khoussainov has also received: * the 2021 Chinese

National Natural Science Foundation The National Natural Science Foundation of China (NSFC; ) is an organization directly affiliated to China's State Council for the management of the National Natural Science Fund. History NSFC was founded in February 1986 by theoretical chemist T ...

grant; * the 2020

Humboldt prize The Humboldt Prize, the Humboldt-Forschungspreis in German, also known as the Humboldt Research Award, is an award given by the Alexander von Humboldt Foundation of Germany to internationally renowned scientists and scholars who work outside of G ...

; * the 2019 Aitken Lecturership; * multiple

JSPS The is an Independent Administrative Institution in Japan, established for the purpose of contributing to the advancement of science in all fields of the natural and social sciences and the humanities.JSPSweb page History The Japan Society for ...

Invitation Fellowships (2001, 2012, and 2014); * multiple

Marsden Fund Marsden grants are the main form of contestable funding for fundamental, 'blue skies' research in New Zealand. Grants are made in all areas of research, in both science and the humanities. The grants are made from the Marsden Fund, which was establ ...

grants (2001, 2004, 2008 and 2012); * the 2002 Research Excellence Award of the

New Zealand Mathematical Society The New Zealand Mathematical Society is a New Zealand based learned society of mathematicians. It is listed by the Royal Society of New Zealand as the affiliate organisation responsible for mathematics research, and by the International Mathematical ...

References

{{DEFAULTSORT:Khoussainov, Bakhadyr Living people Academic staff of the University of Auckland Uzbekistani scientists Cornell University faculty Year of birth missing (living people) Recipients of Marsden grants