Rahul Jain

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

- A. Anshu, R. Jain, N.A Warsi. A unified approach to source and message compression.
- A. Anshu, N.G. Boddu, Naresh Goud Boddu, R. Jain, S.Kundu, P. Mukhopadhyay. Lifting randomized query complexity to randomized communication complexity.
- A. Anshu, R. Jain, N.A Warsi. One shot entanglement assisted classical and quantum communication over noisy quantum channels: A hypothesis testing and convex split approach.
- A. Anshu, R. Jain, N.A 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, 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, R. Jain, N.A Warsi. (2017). A one-shot achievability result for quantum state redistribution.
*IEEE Transactions on Information Theory* - 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* - Mika Göös, R. Jain, Thomas Watson. (2016). Extension Complexity of Independent Set Polytopes.
*Proc. IEEE FOCS* - 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 - M. Santha, D. Gavinsky, S. Sanyal, R. Jain, Jevgenijs Vihrovs, H. Klauck, S.Kundu, T. Lee. Quadratically Tight Relations for Randomized Query Complexity.
*-None-* - A. Anshu, R. Jain, N.A Warsi. A hypothesis testing approach for communication over entanglement assisted compound quantum channel.
*-None-* - A. Anshu, R. Jain, N.A Warsi. A generalized quantum Slepian-Wolf.
*IEEE Transactions on Information Theory*