Split-state non-malleable codes and secret sharing schemes for quantum
messages.
Naresh Goud Boddu, Vipul Goyal, Rahul Jain, João Ribeiro.
IEEE
Transactions on Information Theory (IEEE-TIT), 2025. To appear.
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 1–8, 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.
1287–1306, 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.
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.
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. 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.
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 358–378, 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.