Rahul Jain
Principal Investigator
+65 6516 8826
Rahul Jain


  • Anurag Anshu, M. Tomamichel, R. Jain, Mario Berta. A minimax approach to one-shot entropy inequalities.
  • Anurag Anshu, R. Jain, Alexander Streltsov. Quantum state redistribution with local coherence.
  • Anurag Anshu, R. Jain. Quantum decoupling via efficient `classical' operations and the entanglement cost of one-shot quantum protocols.
  • Farzin Salek, Anurag Anshu, Min-Hsiu Hsieh, R. Jain, Javier R. Fonollosa. One-shot Capacity bounds on the Simultaneous Transmission of Classical and Quantum Information.
  • 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.
  • 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. (2019). On the near-optimality of one-shot classical communication over quantum channels. J. Math. Phys.
  • A. Anshu, R. Jain, NA Warsi. (2019). Building blocks for communication over noisy quantum networks. IEEE Transactions on Information Theory 65 1287-1306
  • A. Anshu, R. Jain, NA Warsi. (2019). A hypothesis testing approach for communication over entanglement assisted compound quantum channel. IEEE Transactions on Information Theory 65 2623-2636
  • A. Anshu, Mario Berta, R. Jain, Marco Tomamichel. (2019). Partially smoothed information measures. IEEE ISIT
  • A. Anshu, R. Jain, NA Warsi. (2019). One-shot measurement compression with quantum side information using shared randomness.. IEEE Transactions on Information Theory
  • A. Anshu, Min-Hsiu Hsieh, R. Jain. (2018). Quantifying Resources in General Resource Theory with Catalysts. Phys. Rev. Lett. 121
  • A. Anshu, R. Jain, NA Warsi. (2018). A generalized quantum Slepian-Wolf. IEEE Transactions on Information Theory 64 1436 - 145
  • A. Anshu, R. Jain, NA Warsi. (2018). A one-shot achievability result for quantum state redistribution. IEEE Transactions on Information Theory 64 1425 - 143
  • Mika Goos, R. Jain, Thomas Watson. (2018). Extension Complexity of Independent Set Polytopes. SIAM Journal of Computing 47 241–269
  • 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, 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
  • A. Anshu, R. Jain, P. Mukhopadhyay, Ala Shayeghi, P. Yao. (2016). New One Shot Quantum Protocols With Application to Communication Complexity. IEEE Transactions on Information Theory 62 7566 - 757
  • 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 26 147–197
  • 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 58 3664 - 366
  • 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
  • R. Jain, Carl A. Miller, Yaoyun Shi. Parallel Device-Independent Quantum Key Distribution. - None -