Rahul JAIN

Associate 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)
COM2-02-02
651 64705

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

Research Areas

  • Security
  • Algorithms & Theory

Research Interests

  • Quantum Computation
  • Information Theory
  • Complexity Theory
  • Communication Complexity
  • Cryptography

Profile

Rahul Jain is 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.

Current Projects

  • One-shot quantum and classical information theory, channel coding, message compression.
  • Application of information theory in communication complexity, direct-sum, direct-product, composition for communication protocols.
  • Quantum complexity theory, parallel repetition, quantum PCP.
  • Circuit lower bounds via information flow arguments.

Selected Publications

  • 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, 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.

  • Anurag Anshu, Rahul Jain and Naqueeb Ahmad Warsi. "A one-shot achievability result for quantum state redistribution." IEEE Transactions of Information Theory (IEEE-TIT), Volume: 64, Issue: 3, March 2018.

  • 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, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi and Penghui Yao. "New One Shot Quantum Protocols with Application to Communication Complexity." IEEE Transactions of Information Theory (IEEE-TIT), Volume: 62, Issue: 12, Dec. 2016.

  • 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 in nite 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 and communication 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 (IEEETIT), vol. 60:10, pp.1-23, 2014.

  • Rahul Jain and Ashwin Nayak. "Short proofs of the quantum Substate Theorem." IEEE Transactions on Information Theory (IEEE-TIT), Volume: 58(6), pp. 3664- 3669, 2012.

  • 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. 59(8), pp. 5171-5178, 2013. In proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1503-1512, 2013.

  • Rahul Jain, Attila Pereszlényi and 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 semide nite 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), 56(1), 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

Teaching (2019/2020)

  • CS4268: Quantum Computing