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

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

**Lifting randomized query complexity to randomized
communication complexity. **

Anurag
Anshu, Naresh B.Goud,
Rahul Jain, Srijita Kundu, Priyanka
Mukhopadhyay

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

Anurag
Anshu, Rahul Jain, Naqueeb Ahmad Warsi

**A Composition Theorem for
Randomized Query Complexity. **

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

**Parallel Device-Independent
Quantum Key Distribution. **

Rahul
Jain, Carl A. Miller, Yaoyun Shi

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

Anurag
Anshu, Rahul Jain, Naqueeb Ahmad Warsi

**A
generalized quantum Slepian-Wolf. **

Anurag
Anshu, Rahul Jain, Naqueeb Ahmad Warsi

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

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

Anurag
Anshu, Rahul Jain, Naqueeb Ahmad Warsi

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

Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi.

**Quantum communication using coherent rejection
sampling. **

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.