Rahul JAIN

COM2-02-02

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

Professor

Ph.D. (Computer Science, Tata Institute of Fundamental Research, Mumbai, India, 2003)
B.Tech. (Electrical & Electronics Engineering), Indian Institute of Technology, Mumbai, India, 1997)

Rahul Jain has been promoted to full Professor from 1 January 2020. He was an Associate Professor at the Computer Science Department of the National University of Singapore (NUS) from July 2013 (Assistant Professor Nov 2008 - July 2013). He obtained his PhD from Tata Institute of Fundamental Research, Mumbai, India in 2003. He was a post doctoral researcher at the University of California at Berkeley, USA from 2004-2006 and at the Institute for Quantum Computing (IQC), University of Waterloo, Canada from 2006-2008. He obtained Bachelor's degree (B-Tech) in Electrical and Electronics Engineering from Indian Institute of Technology, Mumbai (IIT-B), India in 1997. He is a Principle Investigator at the Centre for Quantum Technologies (CQT), Singapore from Nov. 2008.

RESEARCH AREAS

Security

Algorithms & Theory

Complexity Theory
Cryptography
Information Theory & Coding
Quantum Information & Algorithms

RESEARCH INTERESTS

Quantum Computation
Information Theory
Complexity Theory
Communication Complexity
Cryptography

RESEARCH PROJECTS

RESEARCH GROUPS

TEACHING INNOVATIONS

SELECTED PUBLICATIONS

Rahul Jain, Srijita Kundu. A direct product theorem for quantum communication complexity with applications to device-independent QKD. Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021. Conference on Quantum Information Processing (QIP), 2022.
Rahul Jain, Carl A. Miller, Yaoyun Shi. Rahul Jain, Carl A. Miller, Yaoyun Shi. Parallel device-independent quantum key distribution. IEEE Transactions on Information Theory (IEEE-TIT), Volume: 66, Issue: 9, 2020. International Conference of Quantum Cryptography (QCrypt), 2018.
Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi. Building blocks for communication over noisy quantum networks. IEEE Transactions on Information Theory (IEEE-TIT), Volume: 65, Issue: 2, pp. 1287–1306, 2019. IEEE International Symposium on Information Theory (ISIT), 2018. Annual Conference on Quantum Information Processing (QIP), 2018.
Anurag Anshu, Rahul Jain and Naqueeb Ahmad Warsi. "A generalized quantum Slepian-Wolf." IEEE Transactions of Information Theory (IEEE-TIT), 2018. , Volume: 64, Issue: 3, March 2018. Contributed talk at the 17th Asian Quantum Information Science Conference AQIS 2017.
Mika Göös, Rahul Jain and Thomas Watson. "Extension Complexity of Independent Set Polytopes." SIAM Journal of Computing (SICOMP), Volume 47, Issue 1, pp. 241269, February 2018. In Proceedings of The 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 565-572, 2016.
Anurag Anshu, Vamsi Krishna Devabathini and Rahul Jain. "Quantum communication using coherent rejection sampling." Physical Review Letters (PRL), Vol. 119, Issue 12 - 22 September 2017.
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika G o os, Rahul Jain, Robin Kothari, Troy Lee and Miklos Santha. "Separations in communication complexity using cheat sheets and information complexity." In proceedings of The 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 555-564, 2016.
Christopher Perry, Rahul Jain and Jonathan Oppenheim. "Communication tasks with infnite quantum-classical separation." Phys. Rev. Lett. (PRL) 115, 030504, July 2015.
Rahul Jain. "New strong direct product results in communication complexity." Journal of the ACM (JACM), volume 62 Issue 3, Article No. 20, June 2015.
Lila Fontes, Rahul Jain, Iordanis Kerenidis, Sophie Laplante, Mathieu Laurière, Jérémie Roland. "Relative discrepancy does not separate information andcommunication complexity." In proceedings of The 42nd International Colloquium on Automata, Languages, and Programming (ICALP) 2015, vol. 9134, LNCS, pp. 506-516, 2015. ``Best of 2016" by ACM Computing Reviews.
Rahul Jain and Ashwin Nayak. "The space complexity of recognizing well parenthesized expression." IEEE Transactions on Information Theory (IEEE-TIT),vol. 60:10, pp.1-23, 2014.
Rahul Jain, Yaoyun Shi, Zhaohui Wei and Shengyu Zhang. "Efficient protocols for generating bipartite classical distributions and quantum states." IEEE Transactions on Information Theory (IEEE-TIT), vol. 598, pp. 5171-5178, 2013. In proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1503-1512, 2013.
Rahul Jain and Ashwin Nayak. "Short proofs of the quantum Substate Theorem." IEEE Transactions on Information Theory (IEEE-TIT), Volume: 586, pp. 3664- 3669, 2012.
Rahul Jain, Attila Pereszlényiand Penghui Yao. "A direct product theorem for bounded-round public-coin randomized communication complexity." In proceedings of The 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 167-176, 2012.
Rahul Jain and Penghui Yao. "A parallel approximation algorithm for positive semidefnite programming." In Proceedings of the 52nd Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 463-471, 2011.
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay and John Watrous. "QIP = PSPACE." Invited to the Journal of the ACM (JACM). Published as Article no. 30, Volume 58, Issue 6, December 2011. Research highlight in Communications of the ACM (CACM), Vol. 53 No. 12, 2010. "Best Paper Award"at The 42nd ACM Symposium on Theory of Computing (STOC), pp. 573-582, 2010.
Prahladh Harsha, Rahul Jain, David McAllester and Jaikumar Radhakrishnan. "The communication complexity of correlation." IEEE Transactions on Information Theory (IEEE-TIT), 561, pp. 438-449, 2010. In Proceedings of 22nd IEEE Conference on Computational Complexity (CCC), pp. 10-23, 2007.
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen. "A new information theoretic property about quantum states with an application to privacy in quantum communication." Journal of the ACM (JACM), 2009, Volume 56, Issue 6, Article No.: 33. In proceedings of 43rd IEEE Symposium on Foundations of Computer Science (FOCS), 2002, pp. 429-438.
Rahul Jain, Sarvagya Upadhyay and John Watrous. "Two-message quantum interactive proofs are in PSPACE." In Proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS), 2009, pp. 534-543.
Rahul Jain, Hartmut Klauck and Ashwin Nayak. "Direct product theorems for communication complexity via subdistribution bounds." In proceedings of The 40th ACM Symposium on Theory of Computing (STOC), 2008, pp 599-608.
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen. "A lower bound for bounded round quantum communication complexity of set disjointness." In proceedings of 44th IEEE Symposium on Foundations of Computer Science (FOCS), 2003, pp. 220-229.

AWARDS & HONOURS

Award under the "VISITING ADVANCED JOINT RESEARCH FACULTY SCHEME (VAJRA)" 2017-18 by Department of Science and Technology, Government of India (http://www.vajra-india.in/)
"BEST of 2016" by ACM Computing Reviews for paper number 9 in the selected publications list above.
Young Researcher Award, National University of Singapore, 2012
"Best paper award" at the 42nd ACM Symposium on Theory of Computing (STOC) 2010 for paper number 15 in the selected publications list above.
IBM Distinguished Dissertation Award, 2005
TAA-Sasken Best Thesis Award, 2005-2006

MODULES TAUGHT

CS3236

Introduction to Information Theory