1 The Communication Complexity of Correlation (2009)
Prahladh Harsha, Rahul Jain, David Mcallester, Jaikumar Radhakrishnan
Abstract—Let X and Y be finite non-empty sets and (X, Y) a pair of random variables taking values in X × Y. We consider communication protocols between two parties, Alice and Bob, for generating X...
Devdatt Dubhashi Aless, Ro Meit Aless, Ro 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...
Lower Bounds for Adaptive Locally Decodable Codes ∗ (2009)
Amit Deshp, Jaikumar Radhakrishnan
An error-correcting code is said to be locally decodable if a randomized algorithm can recover any single bit of a message by reading only a small number of symbols of a possibly corrupted encoding...
A lower bound for the bounded round quantum communication complexity of set disjointness (2008)
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
We show lower bounds in the multi-party quantum communication complexity model. In this model, there are t parties where the ith party has input Xi ⊆ [n]. These parties communicate with each other...
The communication complexity of pointer chasing\Lambda (2008)
Stephen J. Ponzio, Jaikumar Radhakrishnan, S. Venkatesh
Abstract We study the k-round two-party communication complexity of the pointer chasing problem for fixed k. Damm, Jukna and Sgall [2] showed an upper bound of O(n log(k\Gamma 1) n) for this problem....
Abstract Minimizing Average Latency in Oblivious Routing (2008)
Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan
We consider the problem of minimizing average latency cost while obliviously routing traffic in a network with linear latency functions. This is roughly equivalent to minimizing the function � e...
Sourav Chakraborty, Jaikumar Radhakrishnan, Akumar Raghunathan, Prashant Sasatte
error list-decoding capacity of the q/(q − 1) channel
How to Design Connected Sensor Networks that Are Provably Secure (2008)
Roberto Di Pietro, Luigi V. Mancini, Alessandro Mei, Alessandro Panconesi, Jaikumar Radhakrishnan
Abstract — We give, for the first time, a precise mathematical analysis of the connectivity and security properties of sensor networks that make use of the random pre-distribution of keys. We also...
Abstract Minimizing Average Latency in Oblivious Routing (2008)
Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan
We consider the problem of minimizing average latency cost while obliviously routing traffic in a network with linear latency functions. This is roughly equivalent to minimizing the function � e...
Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen
theorem about relative entropy of quantum states with an
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...
Magnús M. Halldórsson, Jaikumar Radhakrishnan
Abstract. Finding maximum independent sets in graphs with bounded maximum degree ∆ is a well-studied NP-complete problem. We introduce an algorithm schema for improving the approximation of...
Tradeoffs in Depth-Two Superconcentrators (2008)
Chinmoy Dutta, Jaikumar Radhakrishnan
Abstract. An N-superconcentrator is a directed graph with N input vertices and N output vertices and some intermediate vertices, such that for k = 1, 2,..., N, between any set of k input vertices and...
Bounds for Error Reduction with Few Quantum (2008)
Sourav Chakraborty, Jaikumar Radhakrishnan, Akumar Raghunathan
Abstract. We consider the quantum database search problem, where we are given a function f: [N] → {0, 1}, and are required to return an x ∈ [N] (a target address) such that f(x) = 1. Recently,...
Sorting Organization of the article Entropy (2008)
We illustrate the role of information theoretic ideas in combinatorial problems, some of them arising in computer science. We also consider the problem of covering graphs using other graphs, and show...
Devdatt Dubhashi Aless, Ro Mei Aless, Ro 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...
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 rst show how to compute connected and weakly connected...
Jaikumar Radhakrishnan, S. Srinivasa Rao
Abstract. 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...
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 k): We...
Essential Covers of the Cube By Hyperplanes (2007)
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) =...
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...
On Dinur’s Proof of the PCP Theorem (2007)
Jaikumar Radhakrishnan, Madhu Sudan
Probabilistically checkable proofs are proofs that can be checked probabilistically by reading very few bits of the proof. In the early 1990s, it was shown that proofs could be transformed into...
The communication complexity of correlation (2007)
Prahladh Harsha, Rahul Jain, David Mcallester, Jaikumar Radhakrishnan
We examine the communication required for generating random variables remotely. One party Alice will be given a distribution D, and she has to send a message to Bob, who is then required to generate...
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 Dinur’s Proof of the PCP Theorem (2006)
Jaikumar Radhakrishnan, Madhu Sudan
Probabilistically checkable proofs are proofs that can checked probabilistically by reading very few bits of the proof. In the early 1990’s, it was shown that proofs could be transformed into...
Subspace polynomials and list decoding of Reed-Solomon codes (2006)
Eli Ben-sasson, Jaikumar Radhakrishnan
We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson and Guruswami-Sudan bounds [Joh62, Joh63, GS99]. In particular, we show that for arbitrarily...
Subspace polynomials and list decoding of Reed-Solomon codes (2006)
Eli Ben-sasson, Jaikumar Radhakrishnan
We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson and Guruswami-Sudan bounds [Joh62, Joh63, GS99]. In particular, we show that for arbitrarily...
Prahladh Harsha, Rahul Jain, David Mcallester, Jaikumar Radhakrishnan
We examine the communication required for generating random variables remotely. One party Alice will be given a distribution D, and she has to send a message to Bob, who is then required to generate...
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...
Complete partitions of graphs (2005)
Guy Kortsarz, Magnús Halldórsson, Jaikumar Radhakrishnan, Sivaramakrishnan Sivasubramanian
A complete partition of a graph G is a partition of its vertex set in which any two distinct classes are connected by an edge. Let cp(G) denote the maximum number of classes in a complete partition...
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...
23rd Annual Conference On Foundations Of Software Technology And Theoretical Computer Science (2003)
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...
Efficient Algorithms for Abelian group isomorphism and related problems (2003)
Telikepalli, Kavitha, Pandya, Paritosh, Radhakrishnan, Jaikumar
On converting CNF to DNF (2003)
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener
Abstract. We study how big the blow-up in size can be when one switches between the CNF and DNF representations of boolean functions. For a function f: {0, 1} n → {0, 1}, cnfsize(f) denotes the...
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...
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...
Are Bitvectors Optimal? (2000)
Harry Buhrman, Peter Bro Miltersen, Jaikumar Radhakrishnan, Srinivasan Venkatesh, H. Buhrman, P. B. Miltersen, ...
We study the static membership problem: Given a set S of at most n keys drawn from a universe of size m, store it so that queries of the form "Is x in S?" can be answered quickly. We study...
Bounds For Dispersers, Extractors, And Depth-Two (2000)
Superconcentrators Jaikumar Radhakrishnan, Jaikumar Radhakrishnan, Amnon Ta-shma
We show that the size of the smallest depth-two N-superconcentrator is #(N log N/ log log N).
Better lower bounds for monotone threshold formulas (1997)
We show that every monotone formula that computes the threshold function THk,n, 2 ≤ k ≤ n 2, has size at least � � k n 2 n log ( k−1). The same lower bound is shown to hold in the stronger...
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 1−ɛ(d) ) (where...
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, 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...
The Randomized Complexity of Maintaining the Minimum (1996)
Gerth St Lting, 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...
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 1\Gammaffl(d) )...
The Randomized Complexity of Maintaining the Minimum (1996)
Jaikumar Radhakrishnan, Gerth Stlting Brodal, Gerth Stlting Brodal
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, Shiva Chaudhuri, Jaikumar Radhakrishnan, Gerth St��lting Brodal
. 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, Gerth Stølting Brodal, Shiva Chaudhuri, Shiva Chaudhuri, Jaikumar Radhakrishnan, Jaikumar Radhakrishnan
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent...
Directed monotone contact networks for threshold functions (1994)
Jaikumar Radhakrishnan, K. V. Subrahmanyam
In this note we consider the problem of computing threshold functions using directed monotone contact networks. We give constructions of monotone contact networks of size (k − 1)(n − k + 2)...
Sigma\Pi\Sigma threshold formulas (1994)
A ΣΠΣ formula has the form � � � u v w Luvw, where each L is either a variable or a negated variable. In this paper we study the computation of threshold functions by ΣΠΣ formulas. By...
The Complexity of Parallel Prefix Problems on Small Domains (1992)
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...
This document in subdirectoryRS/03/45/ On Converting CNF to DNF
Peter Bro Miltersen, Jaikumar Radhakrishnan, Ingo Wegener, Copyright C, Peter Bro Miltersen, Ingo Wegener, ...
Reproduction of all or part of this work is permitted for educational or research use on condition that this copyright notice is included in any copy. See back inner page for a list of recent BRICS...