**Separating quantum communication and approximate rank. **2017**.**

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

**A new operational interpretation of relative entropy and trace distance
between quantum states. **

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

IEEE Transactions of
Information Theory (IEEE-TIT), 2016. To appear.

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

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

**Multipartite Quantum Correlation and Communication.**

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

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

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

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

Rahul Jain, Carl A. Miller, Yaoyun Shi

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

Anurag Anshu, Rahul
Jain, Naqueeb Ahmad Warsi

Anurag Anshu, Rahul
Jain, Naqueeb Ahmad Warsi

Anurag Anshu, Rahul
Jain, Naqueeb Ahmad Warsi

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

Anurag Anshu, Rahul
Jain, Naqueeb Ahmad Warsi

**Smooth min-max relative entropy based bounds
for one-shot classical and quantum state redistribution. **2017.

Anurag Anshu, Rahul Jain, Naqueeb
Ahmad Warsi.

**Quantum
message compression with applications****. **2014.

Anurag Anshu, Vamsi
Krishna Devabathini, Rahul Jain.

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