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...
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...
Quantum search for multiple items using parallel queries (2004)
Grover, Lov K., Radhakrishnan, Jaikumar
In the quantum database search problem we are required to search for an item in a database. In this paper, we consider a generalization of this problem, where we are provided d identical copes of a...
Is partial quantum search of a database any easier? (2004)
Grover, Lov K., Radhakrishnan, Jaikumar
In this paper, we consider the partial database search problem where given a database on N items, we are required to determine the first k bits of an address x such that f(x)=1. We derive an...
Essential Covers of the Cube By Hyperplanes (2003)
Nathan Linial, Jaikumar Radhakrishnan
A set L of linear polynomials in variables X 1 ; X 2 ; : : : ; X n with real coecients is said to be an essential cover of the cube f0; 1g (E1) For each v 2 f0; 1g , there is a p 2 L such that p(v) =...
23rd Annual Conference On Foundations Of Software Technology And Theoretical Computer Science (2003)
On Converting CNF to DNF (2003)
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener, Fb Informatik Ls
We study how big the blow-up in size can be when one switches between the CNF and DNF representations of boolean functions.
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...
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...
Fast Distributed Algorithms for (Weakly) Connected Dominating Sets and Linear-Size Skeletons (2003)
Devdatt Dubhashi, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan, Aravind Srinivasan
Motivated by routing issues in ad hoc networks, we present polylogarithmic-time distributed algorithms for two problems. Given a network, we first show how to compute connected and weakly connected...
Efficient Algorithms for Abelian group isomorphism and related problems (2003)
Telikepalli, Kavitha, Pandya, Paritosh, Radhakrishnan, Jaikumar
A Note on Scrambling Permutations (2001)
A family F of permutations of [n] is completely k-scrambling [7] if for every sequence hp 1 ; p 2 ; : : : ; p k i of k distinct elements of [n], there is a permutation 2 F with (p 1 ) < (p 2 ) < < (p...
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...
Explicit Deterministic Constructions for Membership in the Bitprobe Model (2001)
Jaikumar Radhakrishnan, S. Srinivasa Rao
We look at time-space tradeoffs for the static membership problem in the bit-probe model. The problem is to represent a set of size up to n from a universe of size m using a small number of bits so...
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...
Analytical Studies of Strategies for Utilization of Cache Memory in Computers (2000)
Majumdar, Satya N., Radhakrishnan, Jaikumar
We analyze quantitatively several strategies for better utilization of the {\em cache} or the {\em {fast access}} memory in computers. We define a performance factor $\alpha$ that denotes the...
Tight Bounds for Depth-Two Superconcentrators (1997)
Jaikumar Radhakrishnan, Amnon Ta-shma
We show that the minimum size of a depth-two N-superconcentrator is Theta(N log 2 N= log log N ). Before this work, optimal bounds were known for all depths except two. For the upper bound, we build...
The Randomized Complexity of Maintaining the Minimum (1996)
Shiva Chaudhuri, Gerth Stlting Brodal, Jaikumar Radhakrishnan
The complexity of maintaining a set under the operations Insert, Delete and FindMin is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost t...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth Stølting Brodal, Jaikumar Radhakrishnan
The complexity of maintaining a set under the operations Insert, Delete and FindMin is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost t...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth Stølting Brodal, Jaikumar Radhakrishnan
. The complexity of maintaining a set under the operations Insert, Delete and FindMin is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost t...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth Stølting Brodal, Jaikumar Radhakrishnan
The complexity of maintaining a set under the operations Insert, Delete and FindMin is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost t...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth Stlting Brodal, Shiva Chaudhuri, Jaikumar Radhakrishnan
The complexity of maintaining a set under the operations Insert, Delete and FindMin is considered. In the comparison model it is shown that any randomized algorithm with expected amortized cost t...
Deterministic Restrictions in Circuit Complexity (1996)
We study the complexity of computing Boolean functions using AND, OR and NOT gates. We show that a circuit of depth d with S gates can be made to output a constant by setting O(S 1Gammaffl(d) )...
Deterministic Restrictions in Circuit Complexity (1996)
Shiva Chaudhuri, Jaikumar Radhakrishnan
We study the complexity of computing Boolean functions using AND, OR and NOT gates. We show that a circuit of depth d with S gates can be made to output a constant by setting O(S 1Gammaffl(d) )...
The Complexity of Parallel Prefix Problems on Small Domains (1995)
Shiva P. Chaudhuri, Jaikumar Radhakrishnan
We show non-trivial lower bounds for several prefix problems in the CRCW PRAM model. The chaining problem is, given a binary input, for each 1 in the input, find the index of the nearest 1 (1) to its...