Sanjay JAIN

COM2-03-59

651 67842

www.comp.nus.edu.sg/~sanjay

Provost's Chair Professor

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

Sanjay Jain is a Professor of Computer Science. He received his B. Tech degree from Indian Institute of Technology, Kharagpur, India in 1986 and his PhD in Computer Science from University of Rochester in 1990. Jain's main research interests are in inductive inference, recursion theory, complexity theory and general theoretical computer science. Dr Jain's research work has been published in various journals such as Journal of Computer and System Sciences, Information and Computation, Theoretical Computer Science, Siam Journal of Computation, and Annals of Pure and Applied Logic, etc. Some of the conferences he has published in include STOC, COLT, ALT, STACS, etc. He serves on the editorial board of Information and Computation, and has served on Program Committee for various conferences such as COLT, ALT, LATA, TAMC, PRICAI, etc. He was program co-chair for ALT 2000 and ALT 2013 and conference chair for ALT 2005. HIs paper with Calude, Khoussainov, Li and Stephan on Deciding Parity Games in Quasipolynomial Time won the STOC 2017 best paper award.

RESEARCH AREAS

Algorithms & Theory

RESEARCH INTERESTS

Inductive Inference
Complexity Theory
Recursion Theory
Computational Learning Theory
Structural Complexity

RESEARCH PROJECTS

RESEARCH GROUPS

TEACHING INNOVATIONS

SELECTED PUBLICATIONS

Deciding Parity Games in Quasipolynomial Time.Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan.Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC, pages 252--263, 2017.Best paper award
Enlarging Learnable Classes.Sanjay Jain, Timo Kotzing and Frank Stephan.In Information and Computation, Vol 251, pages 194--207, 2016.
Learnability of Automatic Classes.Sanjay Jain, Qinglong Luo and Frank Stephan.In Journal of Computer and System Sciences, Volume 78, issue 6, Pages 1910--1927, 2012. Special issue on LATA 2010.
Learning Languages from Positive Data and Negative Counterexamples.Sanjay Jain and Efim Kinber In Journal of Computer and System Sciences, Volume 74, Number 4, Pages 431--456, 2008.Special Issue: Carl Smith Memorial Issue.
Generality's Price: Inescapable Deficiencies in Machine-Learned Programs.John Case, Keh-Jiann Chen, Sanjay Jain, Wolfgang Merkle and James S. Royer.Annals of Pure and Applied Logic, Volume 139, Issues 1--3, Pages 303--326, May 2006.
On Learning to Coordinate: Random Bits Help, Insightful Normal Forms and Competency Isomorphisms.John Case, Sanjay Jain, Franco Montagna, Giulia Simi and Andrea Sorbi.In Journal of Computer and System Sciences, pages 308--332, Volume 71, Number 3, 2005. Special Issue on COLT 2003.
Robust Learning is Rich.Sanjay Jain, Carl Smith, and Rolf Wiehagen.In Journal of Computer and System Sciences, pages 178--212, Volume 62, Number 1, February 2001.
The Synthesis of Language Learners.Ganesh Baliga, John Case and Sanjay Jain.In Information and Computation,pages 16--43, Volume 152, Number 1, July 1999.
Computational Limits on Team Identification of Languages.Sanjay Jain and Arun Sharma.In Information and Computation,pages 19--60, Volume 130, Number 1, October 1996.
The Intrinsic Complexity of Language Identification.Sanjay Jain and Arun Sharma.In the Journal of Computer and System Sciences, pages 393--402, Volume 52, Number 3, June 1996.Special issue on Computational Learning Theory, 1994.