Rahul Jain, Iordanis
Kerenidis, Greg Kuperberg, Miklos Santha, Or Sattath, Shengyu Zhang. On the power of unique quantum witness. 2009. In proceedings of the 1st Annual Conference on
Innovations in Computer Science (ICS), 2010. Conference version. Also available at arXiv:0906.4425.
Prahladh Harsha, Rahul Jain, David
Mc. Allester, Jaikumar Radhakrishnan. The communication complexity of
correlation. IEEE Transactions on Information
Theory, 2009. Full
version
Extended abstract appeared
previously in Proceedings of 22nd IEEE Conference on Computational Complexity
(CCC), pp 10-23, 2007. Also available at ECCC TR06-151.
Rahul Jain, Sarvagya
Upadhyay, John Watrous. Two-message quantum interactive proofs are in
PSPACE. In proceedings of the 50th Annual Symposium on Foundations of Computer Science (FOCS). To appear, 2009. Full version. Also available at arXiv:0905.1300.
Rahul Jain, Hartmut Klauck. New
results in the simultaneous message passing model via information theoretic techniques . In proceedings of the
24th IEEE Conference on Computational Complexity (CCC). To appear, 2009. Conference version. Also
available at arXiv:0902.3056
Rahul Jain, John Watrous. Parallel approximation of non-interactive zero-sum quantum games.
In proceedings of the 24th IEEE Conference on Computational Complexity
(CCC). To appear, 2009. Conference version. Also
available at arXiv:0808.2775
Rahul Jain, Alexandra Kolla, Gatis Midrijanis,
Ben W. Reichardt. On parallel composition of zero-knowledge proofs with black-box quantum
simulators. Quantum Information and Computation
(QIC), Vol.9, No.5&6, pp. 0513-0532, 2009. Journal
version Also available at arXiv:quant-ph/0607211.
Rahul Jain, Shengyu Zhang. New bounds on classical and quantum one-way communication complexity.
Theoretical Computer Science (TCS) 410 (2009), pp. 2463-2477. Journal version. Also available
at arXiv:0802.4101.
Richard Cleve, Dmitry Gavinsky, Rahul Jain. Entanglement-resistant
two-prover interactive proof systems and non-adaptive
private information retrieval systems. Quantum
Information and Computation (QIC), Vol.9 No.7&8, pp. 0648-0656, 2009.
Journal
version Also available at arXiv:0707.1729.
Rahul Jain, Jaikumar
Radhakrishnan and Pranab
Sen. A new
information-theoretic property about quantum states with an application to
privacy in quantum communication. Journal
of ACM (JACM) 2009. Journal version. Also
available at arXiv:0705.2437 .
Many results in the above
paper appeared previously in:
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen. Privacy and interaction in quantum
communication complexity and a theorem about the relative entropy of quantum
states. In Proceedings of the 43rd Annual IEEE
Symposium on Foundations of Computer Science (FOCS), pp 429-438, 2002.
Rahul Jain, Ashwin Nayak, Yi Su. A separation between divergence and Holevo
information for ensembles. In Proceedings of
the Theory and Applications of Models of Computation (TAMC), pp 526-541, 2008.
Invited to a special issue of Mathematical Structures in
Computer Science, London Math Soc., Cambridge University Press, for the
conference TAMC 2008. To appear. Conference version.
Rahul Jain, Hartmut Klauck, Ashwin Nayak. Direct
product theorems for classical communication complexity via subdistribution
bounds. In proceedings of The 40th ACM Symposium on
Theory of Computing (STOC), pp 599-608, 2008. Conference version.
Rahul Jain. New binding-concealing trade-offs for
quantum string commitment. Journal of Cryptology (JoC), Vol. 24 (4), pp 579-592, 2008. Journal
version Also available at arXiv:quant-ph/0506001.
Rahul Jain. Teleportation of Quantum States, **1993; Bennett,
Brassard, Crepeau, Jozsa,
Peres, Wootters. Contributed
article on invitation to Encyclopedia of Algorithms, 2008. Article.
Rahul Jain. Communication complexity of remote state preparation with
entanglement. Quantum Information and
Computation (QIC), Vol 6, no 4&5, pp 461-464,
2006. Journal
version Also available at arXiv:quant-ph/0504008.
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen. Optimal direct sum and privacy trade-off results
for quantum and classical communication complexity. Full version.
Many results in the above
appeared previously in:
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen. Prior entanglement, message compression
and privacy in quantum communication. In Proceedings
of 20th IEEE Conference on Computational Complexity (CCC), pp 285-296, 2005.
Conference version.
Amit Deshpande, Rahul Jain, Satyanarayana V. Lokam, Jaikumar
Radhakrishnan, Kavita Telikapalli. Improved lower bounds for locally decodable codes.
Random Structures and Algorithms, 2004. Extended abstract In Proceedings of the 17th IEEE Conference on
Computational Complexity (CCC), pp 152-161, 2002. Conference version .
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen. A lower bound for bounded round quantum
communication complexity of set disjointness. In Proceedings of the 44th Annual IEEE Symposium on
Foundations of Computer Science (FOCS), page 220, 2003. Conference version. Also available at arXiv:quant-ph/0303138.
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen. A direct sum theorem in communication
complexity via message compression. In Proceedings of
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.
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen. The quantum communication complexity of
the pointer chasing problem: the bit version. In
proceedings of 22nd conference on the Foundations of Software Technology and
Theoretical Computer Science (FSTTCS), pp 218-229, 2002. Conference version.
Rahul Jain, Hartmut Klauck. The Partition Bound for
Classical Communication Complexity and Query Complexity, 2009. Manuscript. Also available at arXiv:0910.4266.
Rahul Jain, Hartmut Klauck, Shengyu Zhang. Depth-Independent
Lower bounds on Communication Complexity of Read-Once Boolean Functions, 2009.
Manuscript Also available at arXiv:0908.4453.
Rahul Jain, Zhengfeng Ji,
Sarvagya Upadhyay, John Watrous. QIP = PSPACE. 2009, Submitted. Manuscript.. Also
available at arXive:0907.4737.
Rahul Jain, Ashwin Nayak. Accessible versus Holevo
information for a binary random variable. Submitted,
2006. Manuscript. Also available at arXiv:quant-ph/0603278.
Rahul Jain. An approach from classical information theory to lower bounds for
smooth codes.
2006. Manuscript.
Also available at arXiv:cs/0607042.
Rahul Jain. Resource requirements of private quantum channels and
consequence for oblivious remote state preparation. Submitted, 2006. Manuscript
Also available at arXiv:quant-ph/0507075.
Rahul Jain. Distinguishing
sets of quantum states. 2005. Manuscript
Also available at arXiv:quant-ph/0506205 .
Rahul Jain. A Super-Additivity Inequality for Channel
Capacity of Classical-Quantum Channels. 2005. Manuscript.
Also available at arXiv:quant-ph/0507088 .