# Rahul Jain

According to our database

Collaborative distances:

^{1}, Rahul Jain authored at least 83 papers between 2002 and 2020.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2020

Quadratically Tight Relations for Randomized Query Complexity.

Theory Comput. Syst., 2020

2019

Convex-Split and Hypothesis Testing Approach to One-Shot Quantum Measurement Compression and Randomness Extraction.

IEEE Trans. Information Theory, 2019

A Hypothesis Testing Approach for Communication Over Entanglement-Assisted Compound Quantum Channel.

IEEE Trans. Information Theory, 2019

Building Blocks for Communication Over Noisy Quantum Networks.

IEEE Trans. Information Theory, 2019

Second-Order Characterizations via Partial Smoothing.

Proceedings of the IEEE International Symposium on Information Theory, 2019

2018

A Generalized Quantum Slepian-Wolf.

IEEE Trans. Information Theory, 2018

A One-Shot Achievability Result for Quantum State Redistribution.

IEEE Trans. Information Theory, 2018

One-shot Capacity bounds on the Simultaneous Transmission of Classical and Quantum Information.

CoRR, 2018

Partially smoothed information measures.

CoRR, 2018

One-shot Capacity Bounds on the Simultaneous Transmission of Public and Private Information Over Quantum Channels.

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

Building Blocks for Communication Over Noisy Quantum Nerworks.

Proceedings of the 2018 IEEE International Symposium on Information Theory, 2018

2017

Special issue on the conference Theory and Applications of Models of Computation.

Inf. Comput., 2017

Quadratically Tight Relations for Randomized Query Complexity.

Electronic Colloquium on Computational Complexity (ECCC), 2017

Lifting randomized query complexity to randomized communication complexity.

Electronic Colloquium on Computational Complexity (ECCC), 2017

A Composition Theorem for Randomized Query complexity.

Electronic Colloquium on Computational Complexity (ECCC), 2017

Measurement compression with quantum side information using shared randomness.

CoRR, 2017

A unified approach to source and message compression.

CoRR, 2017

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

CoRR, 2017

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

CoRR, 2017

Multipartite Quantum Correlation and Communication Complexities.

Computational Complexity, 2017

Information-theoretic approximations of the nonnegative rank.

Computational Complexity, 2017

Matching Multiplications in Bit-Vector Formulas.

Proceedings of the Verification, Model Checking, and Abstract Interpretation, 2017

Achievability bounds on quantum state redistribution using convex split and position based decoding.

Proceedings of the 2017 IEEE Information Theory Workshop, 2017

Separating Quantum Communication and Approximate Rank.

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

Teleportation of Quantum States.

Encyclopedia of Algorithms, 2016

New One Shot Quantum Protocols With Application to Communication Complexity.

IEEE Trans. Information Theory, 2016

Extension Complexity of Independent Set Polytopes.

Electronic Colloquium on Computational Complexity (ECCC), 2016

Separations in communication complexity using cheat sheets and information complexity.

Electronic Colloquium on Computational Complexity (ECCC), 2016

A Direct Product Theorem for Two-Party Bounded-Round Public-Coin Communication Complexity.

Algorithmica, 2016

Partition Bound Is Quadratically Tight for Product Distributions.

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015

New Strong Direct Product Results in Communication Complexity.

J. ACM, 2015

Relaxed partition bound is quadratically tight for product distributions.

Electronic Colloquium on Computational Complexity (ECCC), 2015

Relative Discrepancy does not separate Information and Communication Complexity.

Electronic Colloquium on Computational Complexity (ECCC), 2015

2014

The Space Complexity of Recognizing Well-Parenthesized Expressions in the Streaming Model: The Index Function Revisited.

IEEE Trans. Information Theory, 2014

Approximate and Multipartite Quantum Correlation (Communication) Complexity.

CoRR, 2014

A quadratically tight partition bound for classical communication complexity and query complexity.

CoRR, 2014

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

CoRR, 2014

Near optimal bounds on quantum communication complexity of single-shot quantum state redistribution.

CoRR, 2014

A Parallel Repetition Theorem for Entangled Two-Player One-Round Games under Product Distributions.

Proceedings of the IEEE 29th Conference on Computational Complexity, 2014

Unidirectional Input/Output Streaming Complexity of Reversal and Sorting.

Proceedings of the Approximation, 2014

2013

Efficient Protocols for Generating Bipartite Classical Distributions and Quantum States.

IEEE Trans. Information Theory, 2013

A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound.

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2013

2012

On the Power of a Unique Quantum Witness.

Theory of Computing, 2012

Short Proofs of the Quantum Substate Theorem.

IEEE Trans. Information Theory, 2012

Resource Requirements of Private Quantum Channels and Consequences for Oblivious Remote State Preparation.

J. Cryptology, 2012

A strong direct product theorem in terms of the smooth rectangle bound

CoRR, 2012

Correlation/Communication complexity of generating bipartite states

CoRR, 2012

A parallel approximation algorithm for mixed packing and covering semidefinite programs

CoRR, 2012

A direct product theorem for bounded-round public-coin randomized communication complexity

CoRR, 2012

2011

The Influence Lower Bound Via Query Elimination.

Theory of Computing, 2011

QIP = PSPACE.

J. ACM, 2011

A short proof of the Quantum Substate Theorem

CoRR, 2011

A Parallel Approximation Algorithm for Positive Semidefinite Programming.

Proceedings of the IEEE 52nd Annual Symposium on Foundations of Computer Science, 2011

2010

A separation between divergence and Holevo information for ensembles.

Mathematical Structures in Computer Science, 2010

Optimal direct sum results for deterministic and randomized decision tree complexity.

Inf. Process. Lett., 2010

The space complexity of recognizing well-parenthesized expressions.

Electronic Colloquium on Computational Complexity (ECCC), 2010

A strong direct product theorem for two-way public coin communication complexity

CoRR, 2010

Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity

CoRR, 2010

Depth-Independent Lower Bounds on the Communication Complexity of Read-Once Boolean Formulas.

Proceedings of the Computing and Combinatorics, 16th Annual International Conference, 2010

The Partition Bound for Classical Communication Complexity and Query Complexity.

Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, 2010

2009

New bounds on classical and quantum one-way communication complexity.

Theor. Comput. Sci., 2009

On parallel composition of zero-knowledge proofs with black-box quantum simulators.

Quantum Information & Computation, 2009

Entanglement-resistant two-prover interactive proof systems and non-adaptive pir's.

Quantum Information & Computation, 2009

A property of quantum relative entropy with an application to privacy in quantum communication.

J. ACM, 2009

New Results in the Simultaneous Message Passing Model

CoRR, 2009

Two-Message Quantum Interactive Proofs Are in PSPACE.

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

Parallel Approximation of Non-interactive Zero-sum Quantum Games.

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

New Results in the Simultaneous Message Passing Model via Information Theoretic Techniques.

Proceedings of the 24th Annual IEEE Conference on Computational Complexity, 2009

2008

Teleportation of Quantum States.

Proceedings of the Encyclopedia of Algorithms - 2008 Edition, 2008

New Binding-Concealing Trade-Offs for Quantum String Commitment.

J. Cryptology, 2008

Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity

CoRR, 2008

Direct product theorems for classical communication complexity via subdistribution bounds: extended abstract.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

2007

Direct Product Theorems for Communication Complexity via Subdistribution Bounds.

Electronic Colloquium on Computational Complexity (ECCC), 2007

2006

Communication complexity of remote state preparation with entanglement.

Quantum Information & Computation, 2006

The communication complexity of correlation.

Electronic Colloquium on Computational Complexity (ECCC), 2006

Towards a classical proof of exponential lower bound for 2-probe smooth codes

CoRR, 2006

2005

Lower bounds for adaptive locally decodable codes.

Random Struct. Algorithms, 2005

Prior Entanglement, Message Compression and Privacy in Quantum Communication.

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2003

A Direct Sum Theorem in Communication Complexity via Message Compression.

Proceedings of the Automata, Languages and Programming, 30th International Colloquium, 2003

A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness.

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

The Quantum Communication Complexity of the Pointer Chasing Problem: The Bit Version.

Proceedings of the FST TCS 2002: Foundations of Software Technology and Theoretical Computer Science, 2002

Privacy and Interaction in Quantum Communication Complexity and a Theorem about the Relative Entropy of Quantum States.

Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

Better Lower Bounds for Locally Decodable Codes.

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002