Rahul Jain
Principal Investigator
Centre for Quantum TechnologiesProfessor
Department of Computer Science, School of Computing, National University of Singapore
S15-04-01
Preprints
- Michael X. Cao, R. Jain, M. Tomamichel. Quantum Channel Simulation under Purified Distance is no more difficult than State Splitting.
- R. Jain, João F. Doriguello, Srinivasan Arunachalam. A note on the partition bound for one-way classical communication complexity.
- N.G. Boddu, R. Jain, D. Aggarwal. Quantum secure non-malleable codes in the split-state model.
- Maciej Lukasz Obremski, N.G. Boddu, R. Jain, D. Aggarwal. Quantum Measurement Adversary.
- Anurag Anshu, R. Jain, Alexander Streltsov. Quantum state redistribution with local coherence.
- A. Anshu, 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, T. Lee. A quadratically tight partition bound for classical communication complexity and query complexity.
Publications
- N.G. Boddu, Vipul Goyal, R. Jain, Joao Ribeiro . (2023). Split-State Non-Malleable Codes for Quantum Messages. Annual Conference on Quantum Cryptography (QCrypt)
- N.G. Boddu, R. Jain, R.Batra. (2023). Quantum secure non-malleable randomness encoder and its applications. Annual Conference on Quantum Cryptography (QCrypt)
- N.G. Boddu, R. Jain, Han-Hsuan Lin. (2023). On relating one-way classical and quantum communication complexities. Quantum 7
- Ashwin Nayak, R. Jain, Shima Bab Hadiashar, Anurag Anshu, Dave Touchette. (2023). One-shot quantum state redistribution and quantum Markov chains. IEEE Trans. Inf.
- Ryann Sim, Georgios Piliouras, R. Jain. (2022). Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence. NeurIPS
- N.G. Boddu, R. Jain, Upendra Kapshikar. (2022). Quantum secure non-malleable-extractors. Annual Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC)
- Anurag Anshu, R. Jain. (2022). Efficient methods for one-shot quantum communication. NPJ: Quantum Information
- S.Kundu, R. Jain. (2021). A direct product theorem for quantum communication complexity with applications to device-independent QKD. Proc. IEEE FOCS
- 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
- Swagato Sanyal, M. Santha, T. Lee, R. Jain, H. Klauck, D. Gavinsky, T. Lee, S.Kundu, Jevgenijs Vihrovs. (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 Trans. Inf. 66 2141-2164
- A. Anshu, A. Anshu, Mario Berta, R. Jain, M. Tomamichel. (2020). Partially smoothed information measures. IEEE Trans. Inf. 66 5022-5036
- A. Anshu, A. Anshu, Min-Hsiu Hsieh, R. Jain. (2020). Noisy quantum state redistribution with promise and the Alpha-bit. IEEE Trans. Inf. 66
- R. Jain, Carl A. Miller, Yaoyun Shi. (2020). Parallel Device-Independent Quantum Key Distribution. IEEE Trans. Inf.
- M. Tomamichel, R. Jain, Mario Berta, Anurag Anshu. (2019). A minimax approach to one-shot entropy inequalities. J. Math. Phys. 60
- A. Anshu, A. Anshu, R. Jain, NA Warsi. (2019). On the near-optimality of one-shot classical communication over quantum channels. J. Math. Phys.
- A. Anshu, A. Anshu, R. Jain, NA Warsi. (2019). Building blocks for communication over noisy quantum networks. IEEE Trans. Inf. 65 1287-1306
- A. Anshu, A. Anshu, R. Jain, NA Warsi. (2019). A hypothesis testing approach for communication over entanglement assisted compound quantum channel. IEEE Trans. Inf. 65 2623-2636
- A. Anshu, A. Anshu, R. Jain, NA Warsi. (2019). Convex-Split and Hypothesis Testing Approach to One-Shot Quantum Measurement Compression and Randomness Extraction. IEEE Trans. Inf. 65 5905-5924
- A. Anshu, A. Anshu, Min-Hsiu Hsieh, R. Jain. (2018). Quantifying Resources in General Resource Theory with Catalysts. Phys. Rev. Lett. 121
- A. Anshu, A. Anshu, R. Jain, NA Warsi. (2018). A generalized quantum Slepian-Wolf. IEEE Trans. Inf. 64 1436 - 145
- A. Anshu, A. Anshu, R. Jain, NA Warsi. (2018). A one-shot achievability result for quantum state redistribution. IEEE Trans. Inf. 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, T. Lee, M. Santha, S. Sanyal, Jevgenijs Vihrovs. (2017). Quadratically Tight Relations for Randomized Query Complexity. CSR
- A. Anshu, A. Anshu, D. Gavinsky, R. Jain, S.Kundu, T. Lee, T. Lee, P. Mukhopadhyay, M. Santha, S. Sanyal. (2017). A Composition Theorem for Randomized Query Complexity. FSTTCS
- A. Anshu, A. Anshu, V. Krishna, R. Jain. (2017). Quantum Communication Using Coherent Rejection Sampling. Phys. Rev. Lett. 119 120506
- A. Anshu, A. Anshu, Shalev Ben-David, Ankit Garg, R. Jain, Robin Kothari, T. Lee, 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, A. Anshu, R. Jain, P. Mukhopadhyay, Ala Shayeghi, P. Yao. (2016). New One Shot Quantum Protocols With Application to Communication Complexity. IEEE Trans. Inf. 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, T. Lee, Sebastian Pokutta. (2016). Information-theoretic approximations of the nonnegative rank. Computational Complexity 26 147–197
- A. Anshu, A. Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Goos, R. Jain, Robin Kothari, T. Lee, 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 Trans. Inf. 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 Trans. Inf. 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 Trans. Inf. 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 Trans. Inf. 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
- Ryann Sim, Georgios Piliouras, R. Jain. Matrix Multiplicative Weights Updates in Quantum Zero-Sum Games: Conservation Laws & Recurrence. - None -
