Publications

A one-shot achievability result for quantum state redistribution.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi.

IEEE Transactions on Information Theory (IEEE-TIT), 2017. To appear.

arXiv:1702.02396

 

A composition theorem for randomized query complexity.

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

The 37rd Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2017. To appear. 

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.

21th 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.

The 32th 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

 

Extension complexity of independent set polytopes.

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

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

ECCC:TR16-070

 

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.

In proceedings of The 57th 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.

In proceedings of The 43rd 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.

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

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.

The 18th 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.

The 29th 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

Contributed talk at the 13th 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

The 33rd 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.

The 53rd 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

The 52nd 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.

The 16th 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. 

The 25th 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.

The 42nd 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.

Extended abstract in the proceedings of the 1st 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.

Extended abstract in the proceedings of the 22nd IEEE Conference on Computational Complexity (CCC), pp 10-23, 2007.

 

Two-message quantum interactive proofs are in PSPACE.

Rahul Jain, Sarvagya Upadhyay, John Watrous.

The 50th 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.

The 24th 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.

The 24th 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 .

Many results in the above paper appeared previously in:

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

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

The 43rd 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.

The 40th 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.

 

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

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

Full version , arXiv:0807.1267

Many results in the above appeared previously in:

Prior entanglement, message compression and privacy in quantum communication.

Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.

The 20th 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.

Extended abstract in the proceedings of the 17th 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.

The 44th 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.

The 30th conference on the 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.

The 22nd conference on the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), pp 218-229, 2002.

Conference version.

 

Manuscripts

One-shot entanglement assisted classical and quantum communication over noisy quantum channels: A hypothesis testing and convex split approach.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

21th Annual Conference on Quantum Information Processing (QIP) 2018.

arXiv:1702.01940

 

Quantifying resource in catalytic resource theory. 2017.

Anurag Anshu, Min-Hsiu Hsieh and Rahul Jain.

21th Annual Conference on Quantum Information Processing (QIP) 2018.

arXiv:1708.00381

 

A generalized quantum Slepian-Wolf.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi.

17th Asian Quantum Information Science Conference (AQIS) 2017.

arXiv:1703.09961

 

Lifting randomized query complexity to randomized communication complexity. 2017.

Anurag AnshuNaresh B.Goud, Rahul Jain, Srijita Kundu, Priyanka Mukhopadhyay

arXiv:1703.07521

 

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

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

arXiv:1706.08286

 

 

Parallel device-independent quantum key distribution. 2017.

Rahul Jain, Carl A. Miller, Yaoyun Shi

arXiv:1703.05426

 

A unified approach to source and message compression. 2017.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

arXiv:1707.03619

 

One-shot measurement compression with quantum side information using shared randomness.

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi

arXiv:1703.02342

 

 

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

Rahul Jain, Nisheeth K. Vishnoi, Troy Lee.

Manuscript  ,  arXiv:1401.4512

 

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

Rahul Jain, Penghui Yao

Manuscript , arXiv:1209.0263

 

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

Rahul Jain, Penghui Yao.

Manuscript , arXiv:1201.6090

 

Accessible versus Holevo information for a binary random variable. 2006.

Rahul Jain, Ashwin Nayak.   

Manuscript , arXiv:quant-ph/0603278.

 

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

Rahul Jain.  

Manuscript. , arXiv:cs/0607042.

 

Distinguishing sets of quantum states. 2005.

Rahul Jain.  

Manuscript , arXiv:quant-ph/0506205 .

 

A super-additivity inequality for channel capacity of classical-quantum channels. 2005.

Rahul Jain.

Manuscript. , arXiv:quant-ph/0507088 .