**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), 2020. To appear.

arXiv:1803.03414

**Parallel device-independent quantum key distribution.**

Rahul Jain, Carl A. Miller, Yaoyun Shi.

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

The 8^{th} International Conference
of Quantum Cryptography (QCrypt), 2018.

**Partially smoothed
information measures. **

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

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

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

**A minimax approach to
one-shot entropy inequalities.**

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

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

**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. DOI: 10.1109/TIT.2019.2945800

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

arXiv:1809.07104

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

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

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.

Contributed talk at the 21st Annual
Conference on Quantum Information Processing (QIP), 2018.

**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.

**Quadratically tight relations for randomized
query complexity.**

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

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

**Quantifying resource in catalytic resource
theory**.

Anurag Anshu, Min-Hsiu Hsieh and Rahul Jain.

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

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

**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.

**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.

Contributed talk at the 17th
Asian Quantum Information Science Conference (AQIS) 2017.

**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.

Contributed
talk at the 21st Annual Conference on Quantum Information Processing (QIP)
2018.

**A composition theorem for randomized query complexity. **

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

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

**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.

**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.

**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.

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

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

**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.

**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.

**Information-theoretic
approximations of the nonnegative rank. **

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

**Communication tasks with infinite quantum-classical separation****.**

Christopher Perry, Rahul Jain, Jonathan Oppenheim.

**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.

**``Best of 2016" by ACM Computing Reviews.**

**New
strong direct product results in communication complexity.**

Rahul Jain* *

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

**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.

**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 13^{th} 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 1^{st} 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.

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.

**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.

**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.

**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.

**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.

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

Rahul Jain,
Jaikumar Radhakrishnan and Pranab Sen.

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

**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.

**A Direct Product Theorem for One-Way Quantum
Communication. 2020**

Rahul Jain, Srijita Kundu

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

Anurag Anshu, Rahul
Jain.

arXiv:1809.07056

**Quantum state redistribution with local
coherence. **2018.

arXiv:1804.04915

**A unified approach to source and message
compression. **2017.

Anurag Anshu, Rahul
Jain, Naqueeb Ahmad Warsi arXiv:1707.03619

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

Rahul Jain, Nisheeth
K. Vishnoi, Troy Lee.

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

Rahul Jain, Penghui Yao

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

Rahul Jain, Penghui Yao.

**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.