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
- Anurag Anshu, Dave Touchette, Ashwin Nayak, R. Jain, Shima Bab Hadiashar. (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
- R. Jain, H. Klauck, D. Gavinsky, T. Lee, S.Kundu, Jevgenijs Vihrovs, Swagato Sanyal, M. Santha, T. Lee. (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 -
