Rahul Jain

Principal Investigator

S15-04-01

rahul@comp.nus.edu.sg

+65 6516 8826

Rahul Jain

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

S15-04-01

rahul@comp.nus.edu.sg

+65 6516 8826

Rahul Jain

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

- S.Kundu, R. Jain. A direct product theorem for quantum communication complexity with applications to device-independent QKD.
- Maciej Lukasz Obremski, R. Jain, N.G. Boddu, D. Aggarwal. Quantum Measurement Adversary.
- Anurag Anshu, R. Jain. Quantum decoupling via efficient `classical' operations and the entanglement cost of one-shot quantum protocols.
- Anurag Anshu, R. Jain, Alexander Streltsov. Quantum state redistribution with local coherence.
- A. Anshu, R. Jain, NA Warsi. A unified approach to source and message compression.
- 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.
- R. Jain, Nisheeth K. Vishnoi, T. Lee. A quadratically tight partition bound for classical communication complexity and query complexity.

- Dave Touchette, Ashwin Nayak, R. Jain, Shima Bab Hadiashar, Anurag Anshu. (2021). One-shot quantum state redistribution and quantum Markov chains.
*Annual Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)* - R. Jain. (2021). Chain-rules for channel capacity.
*IEEE International Symposium on Information Theory* - S.Kundu, R. Jain. (2021). A Direct Product Theorem for One-Way Quantum Communication.
*Proceedings of the Computational Complexity Conference* - S.Kundu, Jevgenijs Vihrovs, Swagato Sanyal, M. Santha, T. Lee, H. Klauck, R. Jain, D. Gavinsky. (2020). Quadratically Tight Relations for Randomized Query Complexity.
*Theory of Computing Systems***64**101-119 - Farzin Salek, Anurag Anshu, Min-Hsiu Hsieh, R. Jain, Javier R. Fonollosa. (2020). One-shot Capacity bounds on the Simultaneous Transmission of Classical and Quantum Information.
*IEEE Transactions on Information Theory***66**2141-2164 - A. Anshu, Mario Berta, R. Jain, M. Tomamichel. (2020). Partially smoothed information measures.
*IEEE Transactions on Information Theory***66**5022-5036 - A. Anshu, Min-Hsiu Hsieh, R. Jain. (2020). Noisy quantum state redistribution with promise and the Alpha-bit.
*IEEE Transactions on Information Theory***66** - R. Jain, Carl A. Miller, Yaoyun Shi. (2020). Parallel Device-Independent Quantum Key Distribution.
*IEEE Transactions on Information Theory* - M. Tomamichel, R. Jain, Mario Berta, Anurag Anshu. (2019). A minimax approach to one-shot entropy inequalities.
*J. Math. Phys.***60** - 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, R. Jain, NA Warsi. (2019). Convex-Split and Hypothesis Testing Approach to One-Shot Quantum Measurement Compression and Randomness Extraction.
*IEEE Transactions on Information Theory***65**5905-5924 - 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* - 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* - Gabor 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 Goos, 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, Jeremie Roland. (2015). Relative discrepancy does not separate information and communication complexity.
*Proceedings of ICALP* - Nathanael Francois, R. Jain, Frederic 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. (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