Arrow Research search

Author name cluster

Jaikumar Radhakrishnan

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

29 papers
2 author rows

Possible papers

29

UAI Conference 2021 Conference Paper

Generalized parametric path problems

  • Kshitij Gajjar
  • Girish Varma
  • Prerona Chatterjee
  • Jaikumar Radhakrishnan

Parametric path problems arise independently in diverse domains, ranging from transportation to finance, where they are studied under various assumptions. We formulate a general path problem with relaxed assumptions, and describe how this formulation is applicable in these domains. We study the complexity of the general problem, and a variant of it where preprocessing is allowed. We show that when the parametric weights are linear functions, algorithms remain tractable even under our relaxed assumptions. Furthermore, we show that if the weights are allowed to be non-linear, the problem becomes NP-hard. We also study the multi-dimensional version of the problem where the weight functions are parameterized by multiple parameters. We show that even with two parameters, this problem is NP-hard.

Details

MFCS Conference 2020 Conference Paper

Improved Explicit Data Structures in the Bit-Probe Model Using Error-Correcting Codes

  • Palash Dey
  • Jaikumar Radhakrishnan
  • Santhoshini Velusamy

We consider the bit-probe complexity of the set membership problem: represent an n-element subset S of an m-element universe as a succinct bit vector so that membership queries of the form "Is x ∈ S" can be answered using at most t probes into the bit vector. Let s(m, n, t) (resp. s_N(m, n, t)) denote the minimum number of bits of storage needed when the probes are adaptive (resp. non-adaptive). Lewenstein, Munro, Nicholson, and Raman (ESA 2014) obtain fully-explicit schemes that show that s(m, n, t) = 𝒪((2^t-1)m^{1/(t - min{2⌊log n⌋, n-3/2})}) for n ≥ 2, t ≥ ⌊log n⌋+1. In this work, we improve this bound when the probes are allowed to be superlinear in n, i. e. , when t ≥ Ω(nlog n), n ≥ 2, we design fully-explicit schemes that show that s(m, n, t) = 𝒪((2^t-1)m^{1/(t-{n-1}/{2^{t/(2(n-1))}})}), asymptotically (in the exponent of m) close to the non-explicit upper bound on s(m, n, t) derived by Radhakrishan, Shah, and Shannigrahi (ESA 2010), for constant n. In the non-adaptive setting, it was shown by Garg and Radhakrishnan (STACS 2017) that for a large constant n₀, for n ≥ n₀, s_N(m, n, 3) ≥ √{mn}. We improve this result by showing that the same lower bound holds even for storing sets of size 2, i. e. , s_N(m, 2, 3) ≥ Ω(√m).

Details

FOCS Conference 2019 Conference Paper

Parametric Shortest Paths in Planar Graphs

  • Kshitij Gajjar
  • Jaikumar Radhakrishnan

We construct a family of planar graphs {G n } n≥4, where G_n has n vertices including a source vertex s, a sink vertex t, and edge weights that change linearly with a parameter λ such that, as λ varies in (-∞, +∞), the piece-wise linear cost of the shortest path from s to t has n Ω(logn) pieces. This shows that lower bounds obtained by Carstensen (1983) and Mulmuley & Shah (2001) for general graphs also hold for planar graphs, refuting a conjecture of Nikolova (2009). Gusfield (1980) and Dean (2009) showed that the number of pieces for every n-vertex graph with linear edge weights is n logn+O(1). We generalize this result in two ways. (i) If the edge weights vary as a polynomial of degree at most d, then the number of pieces is n(logn+(α(n)+O(1)) d ), where α(n) is the inverse Ackermann function. (ii) If the edge weights are linear forms of three parameters, then the number of pieces, appropriately defined for R 3, is n((logn) 2 +O(logn)).

Details

FOCS Conference 2014 Conference Paper

Topology Matters in Communication

  • Arkadev Chattopadhyay
  • Jaikumar Radhakrishnan
  • Atri Rudra

We consider the communication cost of computing functions when inputs are distributed among the vertices of an undirected graph. The communication is assumed to be point-to-point: a processor sends messages only to its neighbors. The processors in the graph act according to a pre-determined protocol, which can be randomized and may err with some small probability. The communication cost of the protocol is the total number of bits exchanged in the worst case. Extending recent work that assumed that the graph was the complete graph (with unit edge lengths), we develop a methodology for showing lower bounds that are sensitive to the graph topology. In particular, for a broad class of graphs, we obtain a lower bound of the form Ω(k 2 n), for computing a function of k inputs, each of which is n-bits long and located at a different vertex. Previous works obtained lower bounds of the form Ω(k n). This methodology yields a variety of other results including the following: A tight lower bound (ignoring poly-log factors) for Element Distinctness, settling a question of Phillips, Verbin and Zhang (SODA '12), a distributed XOR lemma, a lower bound for composed functions, settling a question of Phillips et al. , new topology-dependent bounds for several natural graph problems considered by Woodruff and Zhang (DISC '13). To obtain these results we use tools from the theory of metric embeddings and represent the topological constraints imposed by the graph as a collection of cuts, each cut providing a setting where our understanding of two-party communication complexity can be effectively deployed.

Details

FOCS Conference 2012 Conference Paper

Split and Join: Strong Partitions and Universal Steiner Trees for Graphs

  • Costas Busch
  • Chinmoy Dutta
  • Jaikumar Radhakrishnan
  • Rajmohan Rajaraman
  • Srinivasagopalan Srivathsan

We study the problem of constructing universal Steiner trees for undirected graphs. Given a graph G and a root node r, we seek a single spanning tree T of minimum stretch, where the stretch of T is defined to be the maximum ratio, over all terminal sets X, of the cost of the minimal sub-tree T X of T that connects X to r to the cost of an optimal Steiner tree connecting X to r in G. Universal Steiner trees (USTs) are important for data aggregation problems where computing the Steiner tree from scratch for every input instance of terminals is costly, as for example in low energy sensor network applications. graphs with 2 O(√log n) -stretch. We also give a polynomial time We provide a polynomial time UST construction for general polylog(n)-stretch construction for minor-free graphs. One basic building block of our algorithms is a hierarchy of graph partitions, each of which guarantees small strong diameter for each cluster and bounded neighbourhood intersections for each node. We show close connections between the problems of constructing USTs and building such graph partitions. Our construction of partition hierarchies for general graphs is based on an iterative cluster merging procedure, while the one for minor-free graphs is based on a separator theorem for such graphs and the solution to a cluster aggregation problem that may be of independent interest even for general graphs. To our knowledge, this is the first subpolynomial-stretch (o(n ε ) for any ε >; 0) UST construction for general graphs, and the first polylogarithmic-stretch UST construction for minor-free graphs.

Details

SODA Conference 2009 Conference Paper

Finding duplicates in a data stream

  • Parikshit Gopalan
  • Jaikumar Radhakrishnan

Given a data stream of length n over an alphabet [ m ] where n > m, we consider the problem of finding a duplicate in a single pass. We give a randomized algorithm for this problem that uses O ((log m ) 3 ) space. This answers a question of Muthukrishnan [Mut05] and Tarui [Tar07], who asked if this problem could be solved using sub-linear space and one pass over the input. Our algorithm solves the more general problem of finding a positive frequency element in a stream given by frequency updates where the sum of all frequencies is positive. Our main tool is an Isolation Lemma that reduces this problem to the task of detecting and identifying a Dictatorial variable in a Boolean halfspace. We present various relaxations of the condition n > m, under which one can find duplicates efficiently.

Details

FOCS Conference 2008 Conference Paper

Lower Bounds for Noisy Wireless Networks using Sampling Algorithms

  • Chinmoy Dutta
  • Jaikumar Radhakrishnan

We show a tight lower bound of Omega(N\log\log N) on the number of transmissions required to compute several functions (including the parity function and the majority function) in a network of N randomly placed sensors, communicating using local transmissions, and operating with power near the connectivity threshold. This result considerably simplifies and strengthens an earlier result of Dutta, Kanoria Manjunath and Radhakrishnan (SODA 08) that such networks cannot compute the parity function reliably with significantly fewer than N\log \log N transmissions, thereby showing that the protocol with O(N\log \log N) transmissions due to Ying, Srikant and Dullerud (WiOpt 06) is optimal. We also observe that all the lower bounds shown by Evans and Pippenger (SIAM J. on Computing, 1999) on the average noisy decision tree complexity for several functions can be derived using our technique simply and in a unified way.

Details

FOCS Conference 2006 Conference Paper

Subspace Polynomials and List Decoding of Reed-Solomon Codes

  • Eli Ben-Sasson
  • Swastik Kopparty
  • Jaikumar Radhakrishnan

We show combinatorial limitations on efficient list decoding of Reed-Solomon codes beyond the Johnson and Guruswami-Sudan bounds in the works of S. M. Johnson (1962, 1963) and V. Guruswami and M. Sudan (1999). In particular, we show that for arbitrarily large fields F N, |F N | - N, for any delta isin (0, 1), and K = N delta; : middot Existence: there exists a received word w N: F N rarr F N that agrees with a super-polynomial number of distinct degree K polynomials on ap N radicdelta points each; middot Explicit: there exists a polynomial time constructible received word w' N: F N rarr F N that agrees with a super-polynomial number of distinct degree K polynomials, on ap 2 radic(log N) K points each. In both cases, our results improve upon the previous state of the art, which was ap N delta /delta for the existence case in the work J. Justesen and T. Hoboldt (2001), and ap 2N delta for the explicit one in the work of V. Guruswami and M. Sudan (2005). Furthermore, for delta close to 1 our bound approaches the Guruswami-Sudan bound (which is radicNK) and implies limitations on extending their efficient RS list decoding algorithm to larger decoding radius. Our proof method is surprisingly simple. We work with polynomials that vanish on subspaces of an extension field viewed as a vector space over the base field. These sub-space polynomials are a subclass of linearized polynomials that were first studied by O. Ore (1933, 1934) in the 1930s, and later by coding theorists. For us their main attraction is their sparsity and abundance of roots, virtues that recently won them pivotal roles in probabilistically checkable proofs of proximity in the works of E. Ben-Sasson et al. (2004) and E. Ben-Sasson and M. Sudan (2005) and sub-linear proof verification in the work of E. Ben-Sasson et al. (2005)

Details

FOCS Conference 2003 Conference Paper

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

  • Rahul Jain 0001
  • 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 X/sub i/ /spl sube/ [n]. These parties communicate with each other by transmitting qubits to determine with high probability the value of some function F of their combined input (X/sub 1/, .. ., X/sub t/). We consider the class of Boolean valued functions whose value depends only on X/sub 1/ /spl cap/. .. /spl cap/ X/sub t/; that is, for each F in this class there is an f/sub F/: 2/sup [n]/ /spl rarr/ {0, 1}, such that F(X/sub 1/, .. ., X/sub t/) = f/sub F/(X/sub 1/ /spl cap/. .. /spl cap/ X/sub t/). We show that the t-party k-round communication complexity of F is /spl Omega/(s/sub m/(f/sub F/)/(k/sup 2/)), where s/sub m/(f/sub F/) stands for the monotone sensitivity of f/sub F/' and is defined by s/sub m/(f/sub F/) = /sup /spl utri// max/sub S/spl sube//[n] |{i: f/sub F/(S /spl cup/ {i}) /spl ne/ f/sub F/(S)}|. For two-party quantum communication protocols for the set disjointness problem, this implies that the two parties must exchange /spl Omega/(n/k/sup 2/) qubits. An upper bound of O(n/k) can be derived from the O(/spl radic/n) upper bound due to S. Aaronson and A. Ambainis (2003). For k = 1, our lower bound matches the /spl Omega/(n) lower bound observed by H. Buhrman and R. de Wolf (2001) (based on a result of A. Nayak (1999)), and for 2 /spl les/ k /spl Lt/ n/sup 1/4 /, improves the lower bound of /spl Omega/(/spl radic/n) shown by A. Razborov (2002). For protocols with no restrictions on the number of rounds, we can conclude that the two parties must exchange /spl Omega/(n/sup 1/3/) qubits. This, however, falls short of the optimal /spl Omega/ (/spl radic/n) lower bound shown by A. Razborov (2002). Our result is obtained by adapting to the quantum setting the elegant information-theoretic arguments of Z. Bar-Yossef et al. (2002). Using this method we can show similar lower bounds for the L/sub /spl infin// function considered in Z. Bar-Yossef et al. (2002).

Details

MFCS Conference 2003 Conference Paper

On Converting CNF to DNF

  • 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}, \({\mathsf{cnfsize}}\left(f\right)\) denotes the minimum number of clauses in a CNF for f; similarly, \({\mathsf{dnfsize}}\left(f\right)\) denotes the minimum number of terms in a DNF for f. For 0≤ m ≤ 2 n − 1, let \({\mathsf{dnfsize}}\left(m, n\right)\) be the maximum \({\mathsf{dnfsize}}\left(f\right)\) for a function f: {0, 1} n →{0, 1} with \({\mathsf{cnfsize}}\left(f\right) \leq m\). We show that there are constants c 1, c 2 ≥ 1 and ε > 0, such that for all large n and all \(m \in [ \frac{1}{\epsilon}n, 2^{\epsilon{n}}]\), we have $$ 2^{n -- c_1\frac{n}{\log(m/n)}}~ \leq~ {\mathsf{dnfsize}}(m, n) ~\leq~ 2^{n-c_2 \frac{n}{\log(m/n)}}. $$ In particular, when m is the polynomial n c, we get \({\mathsf{dnfsize}} (n^c, n) = 2^{n -\theta(c^{-1}\frac{n}{\log n})}\).

Details

FOCS Conference 2002 Conference Paper

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

  • Rahul Jain 0001
  • Jaikumar Radhakrishnan
  • Pranab Sen

We prove a fundamental theorem about the relative entropy of quantum states, which roughly states that if the relative entropy, S(/spl rho//spl par//spl sigma/)/spl Delta/=Tr /spl rho/(log /spl rho/-log /spl sigma/), of two quantum states /spl rho/ and /spl sigma/ is at most c, then /spl rho//2/sup O(c)/ 'sits inside' /spl sigma/. Using this 'substate' theorem, we give tight lower bounds for the privacy loss of bounded error quantum communication protocols for the index function problem. We also use the 'substate' theorem to give tight lower bounds for the k-round bounded error quantum communication complexity of the pointer chasing problem, when the wrong player starts, and all the log n bits of the kth pointer are desired.

Details

FOCS Conference 2000 Conference Paper

The Quantum Complexity of Set Membership

  • Jaikumar Radhakrishnan
  • Pranab Sen
  • Srinivasan Venkatesh 0001

Studies the quantum complexity of the static set membership problem: given a subset S (|S|/spl les/n) of a universe of size m(/spl Gt/n), store it as a table, T: (0, 1)/sup r//spl rarr/(0, 1), of bits so that queries of the form 'is x in S? ' can be answered. The goal is to use a small table and yet answer queries using a few bit probes. This problem was considered by H. Buhrman et al. (2000), who showed lower and upper bounds for this problem in the classical deterministic and randomised models. In this paper, we formulate this problem in the "quantum bit-probe model". We assume that access to the table T is provided by means of a black-box (oracle) unitary transform O/sub T/ that takes the basis state (y, b) to the basis state |y, b/spl oplus/T(y)>. The query algorithm is allowed to apply O/sub T/ on any superposition of basis states. We show tradeoff results between the space (defined as 2/sup r/) and the number of probes (oracle calls) in this model. Our results show that the lower bounds shown by Buhrman et al. for the classical model also hold (with minor differences) in the quantum bit-probe model. These bounds almost match the classical upper bounds. Our lower bounds are proved using linear algebraic arguments.

Details

FOCS Conference 1998 Conference Paper

Improved Bounds and Algorithms for Hypergraph Two-Coloring

  • Jaikumar Radhakrishnan
  • Aravind Srinivasan

We show that for all large n, every n-uniform hypergraph with at most 0. 7/spl radic/(n/lnn)/spl times/2/sup n/ edges can be two-colored. We, in fact, present fast algorithms that output a proper two-coloring with high probability for such hypergraphs. We also derandomize and parallelize these algorithms, to derive NC/sup 1/ versions of these results. This makes progress on a problem of Erdos (1963), improving the previous-best bound of n/sup 1/3-0(1)//spl times/2/sup n/ due to Beck (1978). We further generalize this to a "local" version, improving on one of the first applications of the Lovasz Local Lemma.

Details

FOCS Conference 1997 Conference Paper

Tight Bounds for Depth-two Superconcentrators

  • Jaikumar Radhakrishnan
  • Amnon Ta-Shma

We show that the minimum size of a depth-two N-superconcentrator is /spl Theta/(Nlog/sup 2/N/loglogN). Before this work, optimal bounds were known for all depths except two. For the upper bound, we build superconcentrators by putting together a small number of disperser graphs; these disperser graphs are obtained using a probabilistic argument. We present two different methods for showing lower bounds. First, we show that superconcentrators contain several disjoint disperser graphs. When combined with the lower bound for disperser graphs due to Kovari, Sos and Turan, this gives an almost optimal lower bound of /spl Omega/(N(log N/loglog N)/sup 2/) on the size of N-superconcentrators. The second method, based on the work of Hansel (1964), gives the optimal lower bound. The method of the Kovari, Sos and Turan can be extended to give tight lower bounds for extractors, both in terms of the number of truly random bits needed to extract one additional bit and in terms of the unavoidable entropy loss in the system. If the input is an n-bit source with min-entropy /spl kappa/ and the output is required to be within a distance of E from uniform distribution, then to extract even a constant number of additional bits, one must invest at least log(n-/spl kappa/)+2 log(1//spl epsiv/)-O(1) truly random bits; to obtain m output bits one must invest at least m-/spl kappa/+2 log(1//spl epsiv/)-O(1). Thus, there is a loss of 2 log(1//spl epsiv/) bits during the extraction. Interestingly in the case of dispersers this loss in entropy is only about loglog(1//spl epsiv/).

Details

FOCS Conference 1993 Conference Paper

Directed vs. Undirected Monotone Contact Networks for Threshold Functions

  • Magnús M. Halldórsson
  • Jaikumar Radhakrishnan
  • K. V. Subrahmanyam 0001

We consider the problem of computing threshold functions using directed and undirected monotone contact networks. Our main results are the following. First, we show that there exist directed monotone contact networks that compute T/sub k//sup n/, 2/spl les/k/spl les/n-1, of size O(k(n-k+2)log(n-k+2)). This bound is almost optimal for small thresholds, since there exists an /spl Omega/(knlog (n/(k-1))) lower bound. Our networks are described explicitly; the previously best upper bound known, obtained from the undirected networks of Dubiner and Zwick, used non-constructive arguments and gave directed networks of size O(k/sup 3. 99/nlog n). Second, we show a lower bound of O(nlogloglog n) on the size of undirected monotone contact networks computing T/sub n-1//sup n/, improving the 2(n-1) lower bound of Markov. Combined with our upper bound result, this shows that directed monotone contact networks compute some threshold functions more easily than undirected networks. >

Details

FOCS Conference 1992 Conference Paper

The Complexity of Parallel Prefix Problems on Small Domains

  • Shiva Chaudhuri
  • Jaikumar Radhakrishnan

The authors study the complexity of some prefix problems in the CRCW PRAM model. The main result is an Omega ( alpha (n)) lower bound for chaining, matching a previous upper bound and solving an open problem. They give reductions to show an Omega ( alpha (n)) lower bound on the complexity of the prefix maxima and range maxima problems even when the domain is (1, .. ., n). An interesting consequence is that prefix maximum is strictly harder than simple maximum. They also give a reduction to show an Omega ( alpha (n)) lower bound on a parenthesis matching problem, matching the upper bound. No lower bounds were previously known for any of these problems. The lower bounds contribute to the study of very fast parallel algorithms by introducing techniques for proving lower bounds for small domain problems. >

Details

FOCS Conference 1991 Conference Paper

Better Bounds for Threshold Formulas

  • Jaikumar Radhakrishnan

The computation of threshold functions using formulas over the basis (AND, OR, NOT) is considered. It is shown that every monotone formula that computes the threshold function T/sub k//sup n/2 >

Details