Publications

Quantum decoupling via efficient `classical' operations and the entanglement cost of one-shot quantum protocols.

Anurag Anshu, Rahul Jain.

npj Quantum Information. 2021. To appear.

arXiv:1809.07056

 

On relating one-way classical and quantum communication complexities.

Naresh Goud Boddu, Rahul Jain, Han-Hsuan Lin.

Asian Quantum Information Science Conference (AQIS), 2021. To appear.

arXiv:2107.11623

 

A direct product theorem for quantum communication complexity with applications to device-independent QKD.

Rahul Jain, Srijita Kundu.

Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2021. To appear.

arXiv:2106.04299

 

One-shot quantum state redistribution and quantum Markov chains

Anurag Anshu, Shima Bab Hadiashar, Rahul Jain, Ashwin Nayak, Dave Touchette.

IEEE International Symposium on Information Theory (ISIT), 2021.

Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC), 2021.

arXiv:2104.08753

 

Chain-rules for channel capacity. 

Rahul Jain.

IEEE International Symposium on Information Theory (ISIT), 2021.

arXiv:0507088

 

A direct product theorem for one-way quantum communication.

Rahul Jain, Srijita Kundu.

IEEE Conference on Computational Complexity (CCC), 2021.

Conference on the Theory of Quantum Computation, Communication, and Cryptography (TQC), 2021.

arXiv:2008.0893

 

Noisy quantum state redistribution with promise and the Alpha-bit.

Anurag Anshu, Min-Hsiu Hsieh and Rahul Jain.

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 66, Issue: 12, 2020.

arXiv:1803.03414

 

Parallel device-independent quantum key distribution.

Rahul Jain, Carl A. Miller, Yaoyun Shi.

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 66, Issue: 9, 2020.

International Conference of Quantum Cryptography (QCrypt), 2018.

arXiv:1703.05426

 

Partially smoothed information measures.

Anurag Anshu, Mario Berta, Rahul Jain, Marco Tomamichel

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 66, Issue: 8, 2020.

IEEE International Symposium on Information Theory (ISIT), 2019.

Beyond I.I.D. in information theory, 2018.

arXiv:1807.05630 

 

A minimax approach to one-shot entropy inequalities.

Anurag Anshu, Mario Berta, Rahul Jain, Marco Tomamichel.

Journal of Mathematical Physics (JMP), 60, 122201, 2019.

arXiv:1906.00333 

 

One-shot capacity bounds on the simultaneous transmission of classical and quantum information.

Farzin Salek, Anurag Anshu, Min-Hsiu Hsieh, Rahul Jain, Javier R. Fonollos.

IEEE Transactions on Information Theory (IEEE-TIT), 2019.

IEEE International Symposium on Information Theory (ISIT), 2018.

arXiv:1809.07104

 

Convex-split and hypothesis testing approach to one-shot quantum measurement compression and randomness extraction.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi.

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 65, Issue: 9, Sept. 2019.

arXiv:1703.02342

 

On the near-optimality of one-shot classical communication over quantum channels.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi.

Journal of Mathematical Physics (JMP) 60, 012204, 2019.

arXiv:1804.09644

 

Building blocks for communication over noisy quantum networks.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi.

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 65, Issue: 2, pp. 1287–1306, 2019.

IEEE International Symposium on Information Theory (ISIT), 2018.

Annual Conference on Quantum Information Processing (QIP), 2018.

arXiv:1702.01940

 

A hypothesis testing approach for communication over entanglement assisted compound quantum channel.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi.

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 65, Issue: 4, pp. 2623–2636, 2019.

IEEE International Symposium on Information Theory (ISIT). 2018.

arXiv:1706.08286

 

Quadratically tight relations for randomized query complexity.

Dmitry Gavinsky, Rahul Jain, Hartmut Klauck, Srijita Kundu, Troy Lee, Miklos Santha, Swagato Sanyal, Jevgenijs Vihrovs.

International Computer Science Symposium in Russia (CSR), 2018.

arXiv:1708.00822

 

Quantifying resource in catalytic resource theory.

Anurag Anshu, Min-Hsiu Hsieh and Rahul Jain.

Physical Review Letters (PRL), Volume:121, Issue:19, November, 2018.

Annual Conference on Quantum Information Processing (QIP) 2018.

arXiv:1708.00381

 

Extension complexity of independent set polytopes.

Mika Göös, Rahul Jain, and Thomas Watson.

SIAM Journal of Computing (SICOMP), Volume 47, Issue 1, pp. 241–269, February 2018.

In proceedings of The 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 565 – 572, 2016.

ECCC:TR16-070

 

A generalized quantum Slepian-Wolf.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi.

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 64, Issue: 3, March 2018.

Asian Quantum Information Science Conference (AQIS) 2017.

arXiv:1703.09961

 

A one-shot achievability result for quantum state redistribution.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi.

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 64, Issue: 3, March 2018.

Annual Conference on Quantum Information Processing (QIP) 2018.

arXiv:1702.02396

 

A composition theorem for randomized query complexity.

Anurag Anshu, Dmitry Gavinsky, Rahul Jain, Srijita Kundu, Troy Lee, Priyanka Mukhopadhyay, Miklos Santha, Swagato Sanyal.

Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2017.

arXiv:1706.00335

 

Quantum communication using coherent rejection sampling.

Anurag Anshu, Vamsi Krishna Devabathini, Rahul Jain.

Physical Review Letters (PRL), Vol. 119, Issue 12 - 22 September 2017.

Annual Conference on Quantum Information Processing (QIP) 2018.

Manuscript 

 

Separating quantum communication and approximate rank.

Anurag Anshu, Shalev Ben-David, Ankit Garg, Rahul Jain, Robin Kothari, Troy Lee.

IEEE Conference on Computational Complexity (CCC), 2017.

arXiv:1611.05754

 

Multipartite quantum correlation and communication.

Rahul Jain, Zhaohui Wei, Penghui Yao, Shengyu Zhang.

Computational Complexity (CC), Volume 26 Issue 1, Pages 199-228, March 2017.

arXiv:1405.6015

 

New one-shot quantum protocols with application to communication complexity.

Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay, Ala Shayeghi, Penghui Yao.

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 62, Issue: 12, 2016.

arXiv:1404.1366

 

Separations in communication complexity using cheat sheets and information complexity.

Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David, Mika Göös, Rahul Jain, Robin Kothari, Troy Lee and Miklos Santha.

Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 555 – 564, 2016.

arXiv:1605.01142

 

Partition bound is quadratically tight for product distributions.

Prahladh Harsha, Rahul Jain, and Jaikumar Radhakrishnan.

International Colloquium on Automata, Languages, and Programming (ICALP), pp. 135:1 135:13, 2016.

ECCC-TR15-199

 

Information-theoretic approximations of the nonnegative rank.

Gábor Braun, Rahul Jain, Troy Lee, Sebastian Pokutta.

Computational Complexity (CC), pp. 1-51, 2016.

Manuscript  , ECCC-TR13-158

 

Communication tasks with infinite quantum-classical separation.

Christopher Perry, Rahul Jain, Jonathan Oppenheim.

Phys. Rev. Lett. (PRL) 115, 030504, July 2015.

arXiv:1407.8217

 

Relative discrepancy does not separate information and communication complexity.

Lila Fontes, Rahul Jain, Iordanis Kerenidis, Mathieu Lauričre, Sophie Laplante, Jérémie Roland.

International Colloquium on Automata, Languages, and Programming (ICALP), vol. 9134, LNCS, pp. 506-516, 2015.

``Best of 2016" by ACM Computing Reviews.

Full version     ,   ECCC-TR15-028

 

New strong direct product results in communication complexity.

Rahul Jain

Journal of the ACM (JACM). Volume 62 Issue 3, Article No. 20, June 2015. 

Manuscript , ECCC-TR11-024

 

The space complexity of recognizing well-parenthesized expression.

Rahul Jain, Ashwin Nayak.

IEEE Transactions of Information Theory (IEEE-TIT), vol. 60:10, pp.1-23, 2014.

Manuscript ,  arXiv:1004.3165,   ECCC-TR10-071

 

Input/Output Streaming Complexity of Reversal and Sorting.

Nathanaël François, Rahul Jain, Frédéric Magniez.

International Workshop on Randomization and Computation (RANDOM), pp. 654-668, 2014.

Manuscript ,  arXiv:1309.0647

 

A parallel repetition theorem for entangled two-player one-round games under product distributions.

Rahul Jain, Attila Pereszlényi, Penghui Yao.

IEEE Conference on Computational Complexity (CCC), pp. 209-216, 2014.

Conference version ,  arXiv:1311.6309

 

Conclusive exclusion of quantum states.

Somshubhro Bandyopadhyay, Rahul Jain , Jonathan Oppenheim, Christopher Perry

Asian Quantum Information Science Conference (AQIS) 2013.

Physical Review A. vol. 89(2), pp. 22336-22349, 2014.

Journal version , arXiv:1306.4683

 

A strong direct product theorem for the tribes function via the smooth-rectangle bound.

Prahladh Harsha, Rahul Jain

Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp. 141-152, 2013.  

Conference version , arXiv:1302.0275

 

Efficient protocols for generating bipartite classical distributions and quantum states.

Rahul Jain, Yaoyun Shi, Zhaohui Wei,  Shengyu Zhang.

IEEE Transactions of Information Theory, Vol 59(8), pp. 5171-5178, 2013.

The ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1503-1512, 2013.

Journal version , arXiv:1203.1153

 

A direct product theorem for bounded-round public-coin randomized communication complexity.

Rahul Jain, Attila Pereszlényi, Penghui Yao.

Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 167-176, 2012.

Conference version, arXiv:1201.1666

 

Short proofs of the quantum Substate Theorem.

Rahul Jain, Ashwin Nayak

IEEE Transactions on Information Theory (IEEE-TIT), Volume: 58(6), pp. 3664 – 3669, 2012.

Journal version, arXiv:1103.6067

 

A parallel approximation algorithm for positive semidefinite programming.

Rahul Jain, Penghui Yao

Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp. 463 – 471, 2011.

Conference version , arXiv:1104.2502

 

The influence lower bound via query elimination.

Rahul Jain, Shengyu Zhang.

Theory of Computation (ToC), Volume 7, Article 10 pp. 147-153, 2011.

Journal version, arXiv:1102.4699, ECCC-TR11-033

 

Resource requirements of private quantum channels and consequences for oblivious remote state preparation.

Rahul Jain.

Journal of Cryptology (JoC), Volume 25, Issue 1, Page 1-13, 2012.

Journal version ,  arXiv:quant-ph/0507075.

 

Optimal direct sum results for deterministic and randomized decision tree complexity.

Rahul Jain, Hartmut Klauck, Miklos Santha.

Information Processing Letter (IPL), 110 (2010), pp. 893-897.

Journal version ,  arXiv:1004.0105 

 

Depth-independent lower bounds on communication complexity of read-once boolean functions.

Rahul Jain, Hartmut Klauck, Shengyu Zhang.

Annual International Computing and Combinatorics Conference (COCOON), pp.54-59, 2010.

Conference version , arXiv:0908.4453.

 

The partition bound for classical communication complexity and query complexity. 

Rahul Jain, Hartmut Klauck. 

IEEE Conference on Computational Complexity (CCC), pp.247-258, 2010. 

Conference version , arXiv:0910.4266.

 

QIP = PSPACE.

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous.

ACM Symposium on Theory of Computing (STOC), 2010.

Recipient of the best paper award.

Invited to the Journal of ACM (JACM). Published as Article no. 30, Volume 58, Issue 6, December 2011.

Research highlight in Communications of the ACM (CACM), Vol. 53 No. 12, 2010.

Conference version, arXiv:0907.4737.

 

On the power of unique quantum witness.

Rahul Jain, Iordanis Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, Shengyu Zhang.

Theory of Computing (ToC), Volume 8, Article 17 pp. 375-400, 2012.

Annual Conference on Innovations in Computer Science (ICS), pp. 471-480, 2010.

Conference version ,  arXiv:0906.4425.

 

The communication complexity of correlation.

Prahladh Harsha, Rahul Jain, David Mc. Allester, Jaikumar Radhakrishnan.

IEEE Transactions on Information Theory (IEEE-TIT), 56(1), pp. 438-449, 2010.

Full version ,  ECCC:TR06-151.

IEEE Conference on Computational Complexity (CCC), pp 10-23, 2007.

 

Two-message quantum interactive proofs are in PSPACE.

Rahul Jain, Sarvagya Upadhyay, John Watrous.

Annual Symposium on Foundations of Computer Science (FOCS).  pp. 534-543, 2009.

Full version ,  arXiv:0905.1300.

 

New results in the simultaneous message passing model via information theoretic techniques.

Rahul Jain, Hartmut Klauck.

IEEE Conference on Computational Complexity (CCC). pp 369-378, 2009.

Conference version ,  arXiv:0902.3056.

 

Parallel approximation of non-interactive zero-sum quantum games.

Rahul Jain, John Watrous.

IEEE Conference on Computational Complexity (CCC). pp. 243-253.  2009. 

Conference version ,  arXiv:0808.2775

 

On parallel composition of zero-knowledge proofs with black-box quantum simulators.

Rahul Jain, Alexandra Kolla, Gatis Midrijanis, Ben W. Reichardt. 

Quantum Information and Computation (QIC), Vol.9, No.5&6, pp. 0513-0532, 2009.

Journal version , arXiv:quant-ph/0607211.

 

New bounds on classical and quantum one-way communication complexity.

Rahul Jain, Shengyu Zhang.

Theoretical Computer Science (TCS) 410, pp. 2463-2477, 2009. 

Journal version , arXiv:0802.4101.

 

Entanglement-resistant two-prover interactive proof systems and non-adaptive private information retrieval systems.

Richard Cleve, Dmitry Gavinsky, Rahul Jain.

Quantum Information and Computation (QIC), Vol.9 No.7&8, pp. 0648-0656, 2009.

Journal version ,  arXiv:0707.1729.

 

A new information-theoretic property about quantum states with an application to privacy in quantum communication.

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

Journal of ACM (JACM), volume 56, issue 6, Article No.: 33, September, 2009. 

Journal version  , arXiv:0705.2437 .

 

Privacy and interaction in quantum communication complexity and a theorem about the relative entropy of quantum states.

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

Annual IEEE Symposium on Foundations of Computer Science (FOCS), pp 429-438, 2002.

 

A separation between divergence and Holevo information for ensembles.

Rahul Jain, Ashwin Nayak, Yi Su.

The Theory and Applications of Models of Computation (TAMC), pp 526-541, 2008.

Special issue of Mathematical Structures in Computer Science (MSCS), for TAMC 2008, Volume, Special Issue 05, pp 977-993, October 2010.

Conference version.

 

Direct product theorems for classical communication complexity via subdistribution bounds.

Rahul Jain, Hartmut Klauck, Ashwin Nayak.

ACM Symposium on Theory of Computing (STOC), pp 599-608, 2008.

Full version.

 

New binding-concealing trade-offs for quantum string commitment.

Rahul Jain.  

Journal of Cryptology (JoC), Vol. 24 (4), pp 579-592, 2008. 

Journal version ,  arXiv:quant-ph/0506001.

 

Teleportation of Quantum States, **1993; Bennett, Brassard, Crepeau, Jozsa, Peres, Wootters.

Rahul Jain.

Contributed article on invitation to Encyclopedia of Algorithms, 2008.

Article.

 

Communication complexity of remote state preparation with entanglement.

Rahul Jain.

Quantum Information and Computation (QIC), Vol 6, no 4&5, pp 461-464, 2006.

Journal version , arXiv:quant-ph/0504008.

 

Prior entanglement, message compression and privacy in quantum communication.

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

IEEE Conference on Computational Complexity (CCC), pp 285-296, 2005.

Conference version.

 

Lower bounds for adaptive locally decodable codes.

Amit Deshpande, Rahul Jain, Satyanarayana V.  Lokam, Jaikumar Radhakrishnan, Kavita Telikapalli.

Random Structures and Algorithms (RSA), Volume 27, Issue 3, pages 358–378, October 2005.

IEEE Conference on Computational Complexity (CCC), pp 152-161, 2002.

Conference version .

 

A lower bound for bounded round quantum communication complexity of set disjointness.

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

Annual IEEE Symposium on Foundations of Computer Science (FOCS), page 220, 2003.

Conference version.  arXiv:quant-ph/0303138.

 

A direct sum theorem in communication complexity via message compression.

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

International Colloquium on Automata Languages and Programming (ICALP), page 187, 2003.

Invited to a special issue of Theoretical Computer Science (TCS) on ICALP 2003.

Conference version.

 

The quantum communication complexity of the pointer chasing problem: the bit version.

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp 218-229, 2002.

Conference version.

 

Manuscripts

 

Quantum secure non-malleable-extractors.

Naresh Goud Boddu, Rahul Jain, Upendra Kapshikar.

arXiv

 

Quantum Measurement Adversary.

Divesh Aggarwal, Naresh Goud Boddu, Rahul Jain, Maciej Obremski.

arXiv

 

Quantum state redistribution with local coherence.

Anurag Anshu, Rahul Jain, Alexander Streltsov.

arXiv

 

A unified approach to source and message compression.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

arXiv

 

A quadratically tight partition bound for classical communication complexity and query complexity.

Rahul Jain, Nisheeth K. Vishnoi, Troy Lee.

arXiv

 

A strong direct product theorem in terms of the smooth rectangle bound.

Rahul Jain, Penghui Yao

arXiv

 

A parallel approximation algorithm for mixed packing and covering semidefinite programs.

Rahul Jain, Penghui Yao

arXiv

 

Accessible versus Holevo information for a binary random variable.

Rahul Jain, Ashwin Nayak.

arXiv

 

An approach from classical information theory to lower bounds for smooth codes.

Rahul Jain.

arXiv

 

Distinguishing sets of quantum states.

Rahul Jain.

arXiv

 

Optimal direct sum and privacy trade-off results for quantum and classical communication complexity.

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

Full version , arXiv