Split-state non-malleable codes and secret sharing schemes for quantum
messages.
Naresh Goud Boddu, Vipul Goyal, Rahul Jain,
Joćo Ribeiro.
Theory of Cryptography Conference (TCC), 2024.
International Conference of Quantum Cryptography (QCrypt),
2023.
Commitments
are equivalent to one-way state generators.
Rishabh Batra,
Rahul Jain.
Annual IEEE Symposium on Foundations of Computer
Science (FOCS), 2024.
International Conference of Quantum Cryptography (QCrypt), 2024.
Quantum
channel simulation under purified distance is no more difficult than state
splitting.
Michael X. Cao,
Rahul Jain, Marco Tomamichel.
IEEE International Symposium on Information
Theory (ISIT), 2024.
Area
law for the maximally mixed ground state in degenerate 1D gapped systems.
Itai Arad, Raz Firanko,
Rahul Jain.
ACM Symposium on Theory
of Computing (STOC), page 1311-1322, 2024.
Conference on the Theory of Quantum
Computation, Communication, and Cryptography (TQC), 2024.
Quantum secure non-malleable-codes in the split-state model.
Divesh Aggarwal, Naresh Goud Boddu,
Rahul Jain.
IEEE Transactions on Information Theory
(IEEE-TIT), pp. 349-371,
Volume: 70, Issue: 1, 2024.
Quantum Measurement Adversary.
Divesh Aggarwal, Naresh Goud Boddu, Rahul Jain,
Maciej Obremski.
IEEE Transactions on Information Theory
(IEEE-TIT), pp. 318-335, Volume: 70, Issue: 1, 2024.
One-shot
non-catalytic distributed purity distillation.
Sayantan Chakraborty, Rahul Jain, Pranab Sen.
The 59th Annual
Allerton Conference on Communication, Control, and Computing (Allerton), pages
18, 2023.
Quantum secure non-malleable randomness encoder and its application.
Rishabh Batra, Naresh Goud Boddu, Rahul Jain.
International Conference of Quantum
Cryptography (QCrypt), 2023.
On relating one-way classical and quantum communication complexities.
Naresh Goud Boddu, Rahul Jain, Han-Hsuan Lin.
Quantum 7, 1010, 2023.
Asian Quantum Information Science Conference (AQIS), 2021.
One-shot quantum state redistribution and quantum Markov chains.
Anurag Anshu, Shima Bab Hadiashar, Rahul Jain,
Ashwin Nayak, Dave Touchette.
IEEE Transactions on Information Theory
(IEEE-TIT), Volume: 69, Issue: 9, pages: 5788 5804, 2023.
IEEE International Symposium on Information
Theory (ISIT), 2021.
Conference on the Theory of Quantum
Computation, Communication, and Cryptography (TQC), 2021.
Matrix multiplicative weights updates in quantum zero-sum games:
conservation laws and recurrence.
Rahul Jain, Georgios Piliouras, Ryann Sim.
Conference on Neural Information Processing
Systems (NeurIPS), 2022.
Quantum secure non-malleable-extractors.
Naresh Goud Boddu, Rahul Jain, Upendra Kapshikar.
Conference on the Theory of Quantum
Computation, Communication and Cryptography (TQC), 2022.
Quantum decoupling via efficient `classical' operations and the
entanglement cost of one-shot quantum protocols.
Anurag Anshu, Rahul Jain.
npj Quantum Information (npj
QI), 8, Article number: 97, 2022.
A direct product theorem for quantum communication complexity with
applications to device-independent QKD.
Rahul Jain, Srijita Kundu.
Annual IEEE Symposium on Foundations of Computer
Science (FOCS), 2021.
Conference on Quantum Information Processing (QIP),
2022.
Chain-rules for channel capacity.
Rahul Jain.
IEEE International Symposium on Information
Theory (ISIT), 2021.
A direct product theorem for one-way quantum communication.
Rahul Jain, Srijita Kundu.
IEEE Conference on Computational Complexity
(CCC), 2021.
Conference on the Theory of Quantum
Computation, Communication, and Cryptography (TQC), 2021.
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), Volume:
66, Issue: 12, 2020.
Parallel device-independent quantum key distribution.
Rahul Jain, Carl A. Miller, Yaoyun Shi.
IEEE Transactions on Information Theory
(IEEE-TIT), Volume:
66, Issue: 9, 2020.
International Conference of Quantum
Cryptography (QCrypt), 2018.
Partially smoothed
information measures.
IEEE Transactions on Information Theory (IEEE-TIT), Volume: 66, Issue: 8,
2020.
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.
IEEE International Symposium on Information
Theory (ISIT), 2018.
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.
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.
12871306, 2019.
IEEE International Symposium on Information
Theory (ISIT), 2018.
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.
26232636, 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.
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.
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. 241269, 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.
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.
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.
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.
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.
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.
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.
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.
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, ECCC
Input/Output Streaming Complexity of Reversal and Sorting.
Nathanaėl Franēois, Rahul Jain, Frédéric Magniez.
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.
IEEE Conference on Computational Complexity
(CCC), pp. 209-216, 2014.
Conclusive exclusion of quantum states.
Somshubhro Bandyopadhyay,
Rahul Jain , Jonathan Oppenheim, Christopher Perry
Asian Quantum Information
Science Conference (AQIS) 2013.
Physical Review A.
vol. 89(2), pp. 22336-22349, 2014.
A strong direct product theorem for the tribes
function via the smooth-rectangle bound.
Prahladh Harsha, Rahul Jain
Foundations of
Software Technology and Theoretical Computer Science (FSTTCS), pp. 141-152,
2013.
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.
A direct product theorem for bounded-round public-coin randomized
communication complexity.
Rahul Jain, Attila Pereszlényi, Penghui Yao.
Annual IEEE Symposium on Foundations of Computer
Science (FOCS), pp. 167-176, 2012.
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.
A
parallel approximation algorithm for positive semidefinite programming.
Rahul Jain, Penghui Yao
Annual IEEE Symposium on Foundations of Computer
Science (FOCS), pp. 463 471, 2011.
The
influence lower bound via query elimination.
Rahul Jain, Shengyu
Zhang.
Theory of Computation (ToC),
Volume 7,
Article 10 pp. 147-153, 2011.
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.
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.
Depth-independent
lower bounds on communication complexity of read-once boolean
functions.
Rahul Jain, Hartmut Klauck, Shengyu Zhang.
Annual International Computing
and Combinatorics Conference (COCOON), pp.54-59, 2010.
The
partition bound for classical communication complexity and query complexity.
Rahul Jain, Hartmut Klauck.
IEEE Conference on
Computational Complexity (CCC), pp.247-258, 2010.
QIP = PSPACE.
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous.
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.
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.
Annual Conference
on Innovations in Computer Science (ICS), pp. 471-480, 2010.
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.
IEEE Conference on
Computational Complexity (CCC), pp 10-23, 2007.
Two-message quantum interactive proofs are in PSPACE.
Rahul Jain, Sarvagya Upadhyay, John Watrous.
Annual Symposium on
Foundations of Computer Science (FOCS).
pp. 534-543, 2009.
New results in the simultaneous message passing model
via information theoretic techniques.
Rahul Jain, Hartmut
Klauck.
IEEE Conference on
Computational Complexity (CCC). pp 369-378, 2009.
Parallel approximation of non-interactive zero-sum
quantum games.
Rahul Jain, John
Watrous.
IEEE Conference on
Computational Complexity (CCC). pp. 243-253.
2009.
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.
New bounds on classical and quantum one-way
communication complexity.
Rahul Jain, Shengyu Zhang.
Theoretical
Computer Science (TCS) 410, pp. 2463-2477, 2009.
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.
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.
Privacy and interaction in quantum communication complexity and a
theorem about the relative entropy of quantum states.
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.
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.
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.
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.
Prior entanglement, message compression and privacy in quantum
communication.
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.
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 358378, October 2005.
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.
Annual IEEE Symposium
on Foundations of Computer Science (FOCS), page 220, 2003.
A direct sum theorem in communication complexity via message
compression.
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.
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.
Foundations of
Software Technology and Theoretical Computer Science (FSTTCS), pp 218-229,
2002.
Robust
and composable device-independent quantum protocols for oblivious transfer and
bit commitment.
Rishabh Batra, Sayantan Chakraborty, Rahul Jain, Upendra Kapshikar.
On
the power of geometrically-local classical and quantum circuits.
Kishor Bharti,
Rahul Jain.
A note on the partition bound for one-way classical communication complexity.
Srinivasan
Arunachalam, Joćo F. Doriguello, Rahul Jain.
Quantum state redistribution with local coherence.
A unified approach to source and message compression.
Anurag Anshu, Rahul
Jain, Naqueeb Ahmad Warsi
A quadratically tight partition bound for
classical communication complexity and query complexity.
Rahul Jain, Nisheeth
K. Vishnoi, Troy Lee.
A strong direct product theorem in terms of the smooth rectangle bound.
Rahul Jain, Penghui Yao
A
parallel approximation algorithm for mixed packing and covering semidefinite
programs.
Rahul Jain, Penghui Yao
Accessible
versus Holevo information for a binary random
variable.
Rahul Jain, Ashwin Nayak.
An approach from classical
information theory to lower bounds for smooth codes.
Rahul Jain.
Distinguishing sets of quantum states.
Rahul Jain.
Optimal direct sum and privacy trade-off results for quantum and
classical communication complexity.
Rahul Jain, Jaikumar Radhakrishnan and Pranab Sen.