Jain, Rahul, Sen, Pranab, Radhakrishnan, Jaikumar
We show optimal Direct Sum result for the one-way entanglement-assisted quantum communication complexity for any relation f subset of X x Y x Z. We show: Q^{1,pub}(f^m) = Omega(m Q^{1,pub}(f)), where...
Jain, Rahul, Radhakrishnan, Jaikumar, Sen, Pranab
We prove the following theorem about relative entropy of quantum states. "Substate theorem: Let rho and sigma be quantum states in the same Hilbert space with relative entropy S(rho|sigma) = Tr rho...
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem (2006)
Radhakrishnan, Jaikumar, Sen, Pranab, Vishwanathan, Sundar
We consider the problem of computing the second elementary symmetric polynomial S^2_n(X) using depth-three arithmetic circuits of the form "sum of products of linear forms". We consider this problem...
Invertible Quantum Operations and Perfect Encryption of Quantum States (2006)
In this note, we characterize the form of an invertible quantum operation, i.e., a completely positive trace preserving linear transformation (a CPTP map) whose inverse is also a CPTP map. The...
We show that measuring any two quantum states by a random POVM, under a suitable definition of randomness, gives probability distributions having total variation distance at least a universal...
Limitations of Quantum Coset States for Graph Isomorphism (2005)
Hallgren, Sean, Roetteler, Martin, Sen, Pranab
It has been known for some time that graph isomorphism reduces to the hidden subgroup problem (HSP). What is more, most exponential speedups in quantum computation are obtained by solving instances...
A note on the power of quantum fingerprinting (2005)
Golynski, Alexander, Sen, Pranab
In this short note, we improve and extend Yao's paper "On the power of quantum fingerprinting" about simulating a classical public coin simultaneous message protocol by a quantum simultaneous message...
On divergence, relative entropy and the substate property (2005)
Jain, Rahul, Radhakrishnan, Jaikumar, Sen, Pranab
In this article we study relationship between three measures of distinguishability of quantum states called as divergence, relative entropy and the substate property.
Radhakrishnan, Jaikumar, Roetteler, Martin, Sen, Pranab
The hidden subgroup problem (HSP) provides a unified framework to study problems of group-theoretical nature in quantum computing such as order finding and the discrete logarithm problem. While it is...
Lower bounds for predecessor searching in the cell probe model (2003)
We consider a fundamental problem in data structures, static predecessor searching: Given a subset S of size n from the universe [m], store S so that queries of the form "What is the predecessor of x...
A direct sum theorem in communication complexity via message compression (2003)
Jain, Rahul, Radhakrishnan, Jaikumar, Sen, Pranab
We prove lower bounds for the direct sum problem for two-party bounded error randomised multiple-round communication protocols. Our proofs use the notion of information cost of a protocol, as defined...
Hidden Translation and Orbit Coset (2003)
Katalin Friedl, G Abor Ivanyos, Fr Eric Magniez, Miklos Santha, Pranab Sen
We give e#cient quantum algorithms for the problems of Hidden Translation and Hidden Subgroup in a large class of non-abelian groups including solvable groups of constant exponent and of constant...
A lower bound for bounded round quantum communication complexity of set disjointness (2003)
Jain, Rahul, Radhakrishnan, Jaikumar, Sen, Pranab
We consider the class of functions whose value depends only on the intersection of the input X_1,X_2, ..., X_t; that is, for each F in this class there is an f_F: 2^{[n]} \to {0,1}, such that...
Quantum testers for hidden group properties (2002)
Friedl, Katalin, Magniez, Frederic, Santha, Miklos, Sen, Pranab
We construct efficient or query efficient quantum property testers for two existential group properties which have exponential query complexity both for their decision problem in the quantum and for...
Depth-3 Arithmetic Circuits for S^2_n(X) and Extensions of the Graham-Pollack Theorem (2001)
Radhakrishnan, Jaikumar, Sen, Pranab, Vishwanathan, Sundar
We consider the problem of computing the second elementary symmetric polynomial S^2_n(X) using depth-three arithmetic circuits of the form "sum of products of linear forms". We consider this problem...
Lower bounds in the quantum cell probe model (2001)
We introduce a new model for studying quantum data structure problems -- the "quantum cell probe model". We prove a lower bound for the static predecessor problem in the address-only version of this...
The Quantum Complexity of Set Membership (2000)
Radhakrishnan, Jaikumar, Sen, Pranab, Venkatesh, S.
We study the quantum complexity of the static set membership problem: given a subset S (|S| \leq n) of a universe of size m (m \gg n), store it as a table of bits so that queries of the form `Is x...
Goodness-of-fit test with nuisance regression and scale
Jana Jurečková, Jan Picek, Pranab Sen
Contiguity, Heavier (lighter) tails, Regression quantiles, Regression rank scores, Regression interquartile range,
Stopping rules, permutation invariance and sufficiency principle
Nitis Mukhopadhyay, Pranab Sen, Bikas Sinha
Permutation-invariant stopping rules, average sample numbers, percentage savings, sequential point estimation, fixed-width confidence interval, normal mean, unknown variance,
Nonparametric test of restricted interchangeability
Interchangeability, Pitman's shift in location alternative, asymptotic relative efficiency, likelihood ratio test, asymptotic normality, permutational distribution,
Effect of the initial estimator on the asymptotic behavior of one-step M-estimator
Influence function, M-estimator, one-step version of M-estimator, random change of time, score function, weak convergence of M-processes,
Robust tests in group sequential analysis: One- and two-sided hypotheses in the linear model
Clinical trial, comparison of two treatments, composite hypothesis, inequality tests, interim analysis, long tailed distribution, M-estimator, Pitman efficiency, power-robustness, repeated tests,...