Sanjay Jain

Sanjay Jain is a Provost's Chair Professor in the Department of Computer Science at the School of Computing, National University of Singapore (NUS). His research focuses on theoretical computer science with particular emphasis on inductive inference, recursion theory, complexity theory, and computational learning theory.

Education:

• B.Tech. in Computer Science from Indian Institute of Technology Kharagpur, India (1986)
• M.S. in Computer Science from University of Rochester, USA (1988)
• Ph.D. in Computer Science from University of Rochester, USA (1990)

Professor Jain's research spans multiple areas of theoretical computer science. His primary contributions are in computational learning theory, where he has made significant advances in understanding the intrinsic complexity of language identification and the limits of inductive inference. His work on recursion theory explores fundamental questions about computability and complexity, while his research in complexity theory addresses structural aspects of computational problems. A notable achievement was his work on "Deciding Parity Games in Quasipolynomial Time," which won the prestigious STOC 2017 best paper award and later the EATCS-IPEC Nerode Prize.

Professor Jain's publication record shows a consistent focus on theoretical foundations of computer science, particularly in learning theory and computational complexity. His recent work has expanded into automatic structures, semiautomatic models, and connections between computational learning and algebraic structures. There is a clear progression from foundational work on language identification to more complex models involving automatic functions, transducers, and connections to mathematical logic.

Scientific Awards:

• STOC 2017 Best Paper Award for "Deciding Parity Games in Quasipolynomial Time"
• EATCS-IPEC Nerode Prize (2021)

Professor Jain has served on the editorial board of Information and Computation and has been actively involved in the academic community through program committee memberships for major conferences including COLT, ALT, LATA, TAMC, and PRICAI. He has held leadership roles as program co-chair for ALT 2000 and ALT 2013, and conference chair for ALT 2005. His work has been supported by various research grants, though specific details are not provided in the available materials.

Professor Jain leads research in theoretical computer science at NUS, where he has built a strong research group focused on computational learning theory and related areas. His work often involves collaborations with researchers from around the world, particularly with Frank Stephan, with whom he has co-authored numerous papers. His research group has made significant contributions to understanding the fundamental limits and possibilities of computational learning models.