Publications (78)
New one shot quantum protocols with application to communication complexity
Anurag Anshu, Rahul Jain, Priyanka Mukhopadhyay +2
On Transitory Queueing
Harsha Honnappa, Rahul Jain, Amy R. Ward
A strong direct product theorem in terms of the smooth rectangle bound
Rahul Jain, Penghui Yao
Separations in communication complexity using cheat sheets and information complexity
Anurag Anshu, Aleksandrs Belovs, Shalev Ben-David +5
Asynchronous Optimization Over Heterogeneous Networks via Consensus ADMM
Sandeep Kumar, Rahul Jain, Ketan Rajawat
Transitory Queueing Networks
Harsha Honnappa, Rahul Jain
Matching Multiplications in Bit-Vector Formulas
Supratik Chakraborty, Ashutosh Gupta, Rahul Jain
Multipartite Quantum Correlation and Communication Complexities
Rahul Jain, Zhaohui Wei, Penghui Yao +1
Conclusive Exclusion of Quantum States
Somshubhro Bandyopadhyay, Rahul Jain, Jonathan Oppenheim +1
A strong direct product theorem for the tribes function via the smooth-rectangle bound
Prahladh Harsha, Rahul Jain
Quantum state redistribution with local coherence
Anurag Anshu, Rahul Jain, Alexander Streltsov
Extension Complexity of Independent Set Polytopes
Mika Göös, Rahul Jain, Thomas Watson
New Results in the Simultaneous Message Passing Model
Rahul Jain, Hartmut Klauck
Correlation/Communication complexity of generating bipartite states
Rahul Jain, Yaoyun Shi, Zhaohui Wei +1
New bounds on classical and quantum one-way communication complexity
Rahul Jain, Shengyu Zhang
Optimal Direct Sum and Privacy Trade-off Results for Quantum and Classical Communication Complexity
Rahul Jain, Pranab Sen, Jaikumar Radhakrishnan
Communication tasks with infinite quantum-classical separation
Christopher Perry, Rahul Jain, Jonathan Oppenheim
Empirical Q-Value Iteration
Dileep Kalathil, Vivek S. Borkar, Rahul Jain
A lower bound for bounded round quantum communication complexity of set disjointness
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
Quantum message compression with applications
Anurag Anshu, Vamsi Krishna Devabathini, Rahul Jain
On divergence, relative entropy and the substate property
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
A hypothesis testing approach for communication over entanglement assisted compound quantum channel
Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi
Conditioned Functional Limits and Applications to Queues
Harsha Honnappa, Rahul Jain, Amy R. Ward
Two-message quantum interactive proofs are in PSPACE
Rahul Jain, Sarvagya Upadhyay, John Watrous
A Game Theoretic Model for the Gaussian Broadcast Channel
Srinivas Yerramalli, Rahul Jain, Urbashi Mitra
A Nash Equilibrium Need Not Exist in the Locational Marginal Pricing Mechanism
Wenyuan Tang, Rahul Jain
The influence lower bound via query elimination
Rahul Jain, Shengyu Zhang
A parallel approximation algorithm for mixed packing and covering semidefinite programs
Rahul Jain, Penghui Yao
On the near-optimality of one-shot classical communication over quantum channels
Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi
Lifting randomized query complexity to randomized communication complexity
Anurag Anshu, Naresh B. Goud, Rahul Jain +2
A theorem about relative entropy of quantum states with an application to privacy in quantum communication
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
Distinguishing sets of quantum states
Rahul Jain
New binding-concealing trade-offs for quantum string commitment
Rahul Jain
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
Reachability in High Treewidth Graphs
Rahul Jain, Raghunath Tewari
A parallel repetition theorem for entangled two-player one-round games under product distributions
Rahul Jain, Attila Pereszlényi, Penghui Yao
Broadcast Channel Games: Equilibrium Characterization and a MIMO MAC-BC Game Duality
Srinivas Yerramalli, Rahul Jain, Urbashi Mitra
A Separation between Divergence and Holevo Information for Ensembles
Rahul Jain, Ashwin Nayak, Yi Su
Vision-based Obstacle Removal System for Autonomous Ground Vehicles Using a Robotic Arm
Khashayar Asadi, Rahul Jain, Ziqian Qin +5
Quadratically Tight Relations for Randomized Query Complexity
Dmitry Gavinsky, Rahul Jain, Hartmut Klauck +5
Empirical Dynamic Programming
William B. Haskell, Rahul Jain, Dileep Kalathil
Depth-Independent Lower bounds on the Communication Complexity of Read-Once Boolean Formulas
Rahul Jain, Hartmut Klauck, Shengyu Zhang
Accessible versus Holevo Information for a Binary Random Variable
Rahul Jain, Ashwin Nayak
Short proofs of the Quantum Substate Theorem
Rahul Jain, Ashwin Nayak
A direct product theorem for bounded-round public-coin randomized communication complexity
Rahul Jain, Attila Pereszlenyi, Penghui Yao
A generalized quantum Slepian-Wolf
Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi
A unified approach to source and message compression
Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi
Mechanism Designs for Stochastic Resources for Renewable Energy Integration
Wenyuan Tang, Rahul Jain
Coalitional Games for Transmitter Cooperation in MIMO Multiple Access Channels
Srinivas Yerramalli, Rahul Jain, Urbashi Mitra
Entanglement-Resistant Two-Prover Interactive Proof Systems and Non-Adaptive Private Information Retrieval Systems
Richard Cleve, Dmitry Gavinsky, Rahul Jain
On parallel composition of zero-knowledge proofs with black-box quantum simulators
Rahul Jain, Alexandra Kolla, Gatis Midrijanis +1
Strong direct product conjecture holds for all relations in public coin randomized one-way communication complexity
Rahul Jain
A Parallel Approximation Algorithm for Positive Semidefinite Programming
Rahul Jain, Penghui Yao
Parallel approximation of non-interactive zero-sum quantum games
Rahul Jain, John Watrous
Learning Unknown Markov Decision Processes: A Thompson Sampling Approach
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar +1
A one-shot achievability result for quantum state redistribution
Anurag Anshu, Rahul Jain, Naqueeb Ahmad Warsi
An Empirical Dynamic Programming Algorithm for Continuous MDPs
William B. Haskell, Rahul Jain, Hiteshi Sharma +1
Separating quantum communication and approximate rank
Anurag Anshu, Shalev Ben-David, Ankit Garg +3
Towards a classical proof of exponential lower bound for 2-probe smooth codes
Rahul Jain
Stochastic dominance-constrained Markov decision processes
William B. Haskell, Rahul Jain
Combinatorial Network Optimization with Unknown Variables: Multi-Armed Bandits with Linear Rewards
Yi Gai, Bhaskar Krishnamachari, Rahul Jain
QIP = PSPACE
Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay +1
Communication complexity of remote state preparation with entanglement
Rahul Jain
A strong direct product theorem for two-way public coin communication complexity
Rahul Jain
On the power of a unique quantum witness
Rahul Jain, Iordanis Kerenidis, Greg Kuperberg +3
The space complexity of recognizing well-parenthesized expressions in the streaming model: the Index function revisited
Rahul Jain, Ashwin Nayak
A quadratically tight partition bound for classical communication complexity and query complexity
Rahul Jain, Troy Lee, Nisheeth K. Vishnoi
Resource requirements of private quantum channels and consequence for oblivious remote state preparation
Rahul Jain
Optimal Decentralized Control with Asymmetric One-Step Delayed Information Sharing
Naumaan Nayyar, Dileep Kalathil, Rahul Jain
A Two Stage Mechanism For Selling Random Power
Nathan Dahlin, Rahul Jain
On Regret-Optimal Learning in Decentralized Multi-player Multi-armed Bandits
Naumaan Nayyar, Dileep Kalathil, Rahul Jain
A Composition Theorem for Randomized Query Complexity
Anurag Anshu, Dmitry Gavinsky, Rahul Jain +5
Improved direct sum theorem in classical communication complexity
Rahul Jain
Quantifying resource in catalytic resource theory
Anurag Anshu, Min-Hsiu Hsieh, Rahul Jain
A direct sum theorem in communication complexity via message compression
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
The Partition Bound for Classical Communication Complexity and Query Complexity
Rahul Jain, Hartmut Klauck
Optimal Direct Sum Results for Deterministic and Randomized Decision Tree Complexity
Rahul Jain, Hartmut Klauck, Miklos Santha
Unidirectional Input/Output Streaming Complexity of Reversal and Sorting
Nathanaël François, Rahul Jain, Frederic Magniez