Rahul Jain
Principal Investigator
Rahul Jain

Short bio

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.

Website: https://www.comp.nus.edu.sg/~rahul


  • Alexander Streltsov, R. Jain, Anurag Anshu. Quantum state redistribution with local coherence.
  • , R. Jain, Anurag Anshu. Quantum decoupling via efficient `classical' operations and the entanglement cost of one-shot quantum protocols.
  • Javier R. Fonollosa, Farzin Salek, Anurag Anshu, Min-Hsiu Hsieh, R. Jain. One-shot Capacity bounds on the Simultaneous Transmission of Classical and Quantum Information.
  • A. Anshu, R. Jain, NA Warsi. On the near-optimality of one-shot classical communication over quantum channels.
  • A. Anshu, Mario Berta, R. Jain, Marco Tomamichel. Partially smoothed information measures.
  • A. Anshu, Min-Hsiu Hsieh, R. Jain. Noisy quantum state redistribution with promise and the Alpha-bit.
  • A. Anshu, R. Jain, NA Warsi. A unified approach to source and message compression.
  • A. Anshu, R. Jain, NA Warsi. Measurement compression with quantum side information using shared randomness.
  • R. Jain, Carl A. Miller, Yaoyun Shi. Parallel Device-Independent Quantum Key Distribution.
  • R. Jain, Nisheeth K. Vishnoi, T. Lee. A quadratically tight partition bound for classical communication complexity and query complexity.
  • R. Jain, P. Yao. A strong direct product theorem in terms of the smooth rectangle bound.
  • R. Jain, P. Yao. A parallel approximation algorithm for mixed packing and covering semidefinite programs.


  • A. Anshu, R. Jain, NA Warsi. (2018). Building blocks for communication over noisy quantum networks. IEEE Transactions on Information Theory
  • A. Anshu, R. Jain, NA Warsi. (2018). A hypothesis testing approach for communication over entanglement assisted compound quantum channel. IEEE Transactions on Information Theory
  • A. Anshu, Min-Hsiu Hsieh, R. Jain. (2018). Quantifying resource in catalytic resource theory. Phys. Rev. Lett.
  • A. Anshu, R. Jain, NA Warsi. (2018). A generalized quantum Slepian-Wolf. IEEE Transactions on Information Theory
  • A. Anshu, R. Jain, NA Warsi. (2018). A one-shot achievability result for quantum state redistribution. IEEE Transactions on Information Theory
  • , Mika Goos, R. Jain, Thomas Watson. (2018). Extension Complexity of Independent Set Polytopes. SIAM Journal of Computing
  • D. Gavinsky, R. Jain, H. Klauck, S.Kundu, T. Lee, M. Santha, S. Sanyal, Jevgenijs Vihrovs. (2017). Quadratically Tight Relations for Randomized Query Complexity. CSR
  • A. Anshu, D. Gavinsky, R. Jain, S.Kundu, T. Lee, P. Mukhopadhyay, M. Santha, S. Sanyal. (2017). A Composition Theorem for Randomized Query Complexity. FSTTCS 2017
  • A. Anshu, V. Krishna, R. Jain. (2017). Quantum Communication Using Coherent Rejection Sampling. Phys. Rev. Lett. 119 120506
  • A. Anshu, R. Jain, P. Mukhopadhyay, Ala Shayeghi, P. Yao. (2017). A new operational interpretation of relative entropy and trace distance between quantum states. IEEE Transactions on Information Theory
  • A. Anshu, Shalev Ben-David, Ankit Garg, R. Jain, Robin Kothari, T. Lee. (2017). Separating quantum communication and approximate rank. Proc. IEEE CCC
  • R. Jain, Z.H. Wei, Penghui Yao, S. Zhang. (2017). Multipartite Quantum Correlation and Communication Complexities. Computational Complexity 26 199--228
  • Prahladh Harsha, R. Jain, Jaikumar Radhakrishnan. (2016). Partition bound is quadratically tight for product distributions. Proceedings of ICALP
  • Gábor Braun, R. Jain, T. Lee, Sebastian Pokutta. (2016). Information-theoretic approximations of the nonnegative rank. Computational Complexity 1-50
  • A. Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, R. Jain, Robin Kothari, T. Lee, M. Santha. (2016). Separations in communication complexity using cheat sheets and information complexity. Proc. IEEE FOCS 555-564
  • R. Jain. (2016). New strong direct product results in communication complexity. JACM 62
  • Christopher Perry, R. Jain, J. Oppenheim. (2015). Communication tasks with infinite quantum-classical separation. Phys. Rev. Lett. 115 030504
  • Lila Fontes, R. Jain, I. Kerenidis, Sophie Laplante, Mathieu Laurier, Jérémie Roland. (2015). Relative discrepancy does not separate information and communication complexity. Proceedings of ICALP
  • Nathanaël François, R. Jain, Frédéric Magniez. (2014). Input/Output Streaming Complexity of Reversal and Sorting. RANDOM 654-668
  • R. Jain, A. Pereszlenyi, P. Yao. (2014). A parallel repetition theorem for entangled two-player one-round games under product distributions. Proc. IEEE CCC 209-216
  • A. Nayak, R. Jain. (2014). The space complexity of recognizing well-parenthesized expressions in the streaming model: the Index function revisited. IEEE Transactions on Information Theory 60 1-23
  • Somshubhro Bandyopadhyay, R. Jain, J. Oppenheim, Christopher Perry. (2014). Conclusive Exclusion of Quantum States. Phys. Rev. A 89 22336-2234
  • R. Jain, Yaoyun Shi, Z.H. Wei, S. Zhang. (2013). Efficient protocols for generating bipartite classical distributions and quantum states. IEEE Transactions on Information Theory 59 5171-5178
  • , Prahladh Harsha, R. Jain. (2013). A strong direct product theorem for the tribes function via the smooth-rectangle bound. Proceedings of FSTTCS 141-152
  • R. Jain, I. Kerenidis, Greg Kuperberg, M. Santha, Or Sattah, S. Zhang, Name of non-CQT author. (2012). On the power of a unique quantum witness. Theory of Computing 8 375-400
  • R. Jain, Yaoyun Shi, Z.H. Wei, S. Zhang. (2012). Correlation/Communication complexity of generating bipartite states. Symposium on Discrete Algorithms
  • R. Jain, A. Pereszlenyi, P. Yao. (2012). A direct product theorem for bounded-round public-coin randomized communication complexity. Proc. IEEE FOCS
  • R. Jain, A. Nayak. (2012). A short proof of the Quantum Substate Theorem. IEEE Transactions on Information Theory
  • R. Jain, S. Zhang. (2011). The influence lower bound via query elimination. Theory of Computing
  • R. Jain, P. Yao. (2011). A Parallel Approximation Algorithm for Positive Semidefinite Programming. Proc. IEEE FOCS
  • R. Jain. (2010). Resource requirements of private quantum channels and consequences for oblivious remote state preparation. Journal of Cryptology 1-13
  • R. Jain, H. Klauck, M. Santha. (2010). Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity. Inf. Proc. Lett 110 893-897
  • R. Jain, Z. Ji, S. Upadhyay, J. Watrous. (2010). QIP = PSPACE. Proceedings of ACM STOC 573-582
  • R. Jain, H. Klauck. (2010). The Partition Bound for Classical Communication Complexity and Query Complexity. Proc. IEEE CCC 247
  • R. Jain, H. Klauck, S. Zhang. (2010). Depth-Independent Lower bounds on Communication Complexity of Read-Once Boolean Functions. COCOON 16
  • P. Harsha, R. Jain, D.M. Allester, J. Radhakrishnan. (2009). The communication complexity of correlation. IEEE Transactions on Information Theory 56 438 - 449
  • R. Jain, S. Zhang. (2009). New bounds on classical and quantum one-way communication complexity. Theoretical Computer Science 410 2463-2477
  • , R. Cleve, D. Gavinsky, R. Jain. (2009). Entanglement-resistant two-prover interactive proof systems and non-adaptive private information retrieval systems. Quantum Information and Computation 9 648-656
  • R. Jain, J. Radhakrishnan, P. Sen. (2009). A new information-theoretic property about quantum states with an application to privacy in quantum communication. JACM 56
  • R. Jain, A. Kolla, G. Midrijanis, B.W. Reichardt. (2009). On parallel composition of zero-knowledge proofs with black-box quantum simulators. Quantum Information and Computation 9 513-532
  • R. Jain, J. Watrous. (2009). Parallel approximation of non-interactive zero-sum quantum games. Proc. IEEE CCC 243-253
  • R. Jain, H. Klauck. (2009). New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques. Proc. IEEE CCC 369-378
  • R. Jain, S. Upadhyay, J. Watrous. (2009). Two-message quantum interactive proofs are in PSPACE. Proc. IEEE FOCS
  • R. Jain. (2008). New binding-concealing trade-offs for quantum string commitment. Journal of Cryptology 24 579-592
  • R. Jain, A. Nayak, Y. Su. (2008). A separation between divergence and Holevo information for ensembles. Theory and Applications of Models of Computation 526-541
  • R. Jain, H. Klauck, A. Nayak. (2008). Direct product theorems for classical communication complexity via subdistribution bounds. Proceedings of ACM STOC 599-608
  • R. Jain. (2006). Communication complexity of remote state preparation with entanglement. Quantum Information and Computation 6 461-464
  • R. Jain, J. Radhakrishnan, P. Sen. (2005). Prior entanglement, message compression and privacy in quantum communication. Proc. IEEE CCC 285-296
  • R. Jain, J. Radhakrishnan, P. Sen. (2003). A direct sum theorem in communication complexity via message compression. Proceedings of ICALP 187
  • R. Jain, J. Radhakrishnan, P. Sen. (2003). A lower bound for bounded round quantum communication complexity of set disjointness. Proc. IEEE FOCS 220
  • R. Jain, J. Radhakrishnan, P. Sen. (2002). The quantum communication complexity of the pointer chasing problem: the bit version. Proceedings of FSTTCS 218-229
  • A. Deshpande, R. Jain, S.V. Lokam, J. Radhakrishnan, K. Telikapalli. (2002). Improved lower bounds for locally decodable codes. Proc. IEEE CCC 152-161
  • R. Jain, J. Radhakrishnan, P. Sen. (2002). Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states. Proc. IEEE FOCS 429-438