Arrow Research search

Author name cluster

Ashok K. Chandra

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.

19 papers
2 author rows

Possible papers

19

TCS Journal 1990 Journal Article

Communication complexity of PRAMs

  • Alok Aggarwal
  • Ashok K. Chandra
  • Marc Snir

We propose a model, LPRAM, for parallel random access machines with local memory that captures both the communication and computational requirements in parallel computation. For this model, we present several interesting results, including the following: Two n × n matrices can be multiplied in 0(n 3/p) computation time and 0(n2/p 2 3 ) communication steps using p processors (for p = 0(n3/log 3 2 n)). Furthermore, these bounds are optimal for arithmetic on semirings (using +, × only). It is shown that any algorithm that uses comparisons only and that sorts n words requires Ω(n log n/(p log(n/p))) communication steps for 1 < p < n. We also provide an algorithm that sorts n words and uses (-)(n log n/p) computation time and (-)(n log n/p log(n/p))) communication steps. These bounds also apply for computing an n-point FFT graph. It is shown that computing any binary tree τ with n nodes and height h requires Ω(n/p + log n + √h) communication steps, and can always be computed in 0(n/p + min(√n, h)) steps. We also present a simple linear-time algorithm that generates a schedule for computing τ in at most 2D opt(τ) steps, where D opt(τ) represents the minimum communication delay for computing τ. It is also shown that various problems that are expressed as DAGs exhibit a communication-delay/computation-time trade-off.

Details DOI

STOC Conference 1987 Conference Paper

A Model for Hierarchical Memory

  • Alok Aggarwal
  • Bowen Alpern
  • Ashok K. Chandra
  • Marc Snir

In this paper we introduce the Hierarchical Memory Model (HMM) of computation. It is intended to model computers with multiple levels in the memory hierarchy. Access to memory location x is assumed to take time ⌈ log x ⌉. Tight lower and upper bounds are given in this model for the time complexity of searching, sorting, matrix multiplication and FFT. Efficient algorithms in this model utilize locality of reference by bringing data into fast memory and using them several times before returning them to slower memory. It is shown that the circuit simulation problem has inherently poor locality of reference. The results are extended to HMM's where memory access time is given by an arbitrary (nondecreasing) function. Tight upper and lower bounds are obtained for HMM's with polynomial memory access time; the algorithms for searching, FFT and matrix multiplication are shown to be optimal for arbitrary memory access time. On-line memory management algorithms for the HMM model are also considered. An algorithm that uses LRU policy at the successive “levels” of the memory hierarchy is shown to be optimal.

Details

FOCS Conference 1987 Conference Paper

Hierarchical Memory with Block Transfer

  • Alok Aggarwal
  • Ashok K. Chandra
  • Marc Snir

In this paper we introduce a model of Hierarchical Memory with Block Transfer (BT for short). It is like a random access machine, except that access to location x takes time f(x), and a block of consecutive locations can be copied from memory to memory, taking one unit of time per element after the initial access time. We first study the model with f(x) = xα for 0 ≪ α ≪ 1. A tight bound of θ(n log log n) is shown for many simple problems: reading each input, dot product, shuffle exchange, and merging two sorted lists. The same bound holds for transposing a √n × √n matrix; we use this to compute an FFT graph in optimal θ(n log n) time. An optimal θ(n log n) sorting algorithm is also shown. Some additional issues considered are: maintaining data structures such as dictionaries, DAG simulation, and connections with PRAMs. Next we study the model f(x) = x. Using techniques similar to those developed for the previous model, we show tight bounds of θ(n log n) for the simple problems mentioned above, and provide a new technique that yields optimal lower bounds of Ω(n log2n) for sorting, computing an FFT graph, and for matrix transposition. We also obtain optimal bounds for the model f(x)= xα with α ≫ 1. Finally, we study the model f(x) = log x and obtain optimal bounds of θ(n log*n) for simple problems mentioned above and of θ(n log n) for sorting, computing an FFT graph, and for some permutations.

Details

STOC Conference 1983 Conference Paper

Multi-Party Protocols

  • Ashok K. Chandra
  • Merrick L. Furst
  • Richard J. Lipton

Many different types of inter-process communication have been examined from a complexity point of view [SP, Y]. We study a new model, in which a collection of processes P 0 , ..., P k−1 that share information about a set of integers {a 0 , ...,a k−1 }, communicate to determine a 0-1 predicate of the numbers. In this new model, tremendous sharing of information is allowed, while no single party is given enough information to determine the predicate on its own. Formally, each P i has access to every a j except for a i . For simplicity, we only allow the parties to communicate as follows.

Details

STOC Conference 1983 Conference Paper

Unbounded Fan-in Circuits and Associative Functions

  • Ashok K. Chandra
  • Steven Fortune
  • Richard J. Lipton

We consider the computation of finite semigroups using unbounded fan-in circuits. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup in fact does not contain a group, then for any primitive recursive function f , circuits of size O ( nf −1 ( n )) and constant depth exist for the semigroup product of n elements. The depth depends upon the choice of the primitive recursive function f . The circuits not only compute the semigroup product, but every prefix of the semigroup product. A consequence is that the same bounds apply for circuits computing the sum of two n -bit numbers.

Details

FOCS Conference 1982 Conference Paper

A Complexity Theory for Unbounded Fan-In Parallelism

  • Ashok K. Chandra
  • Larry J. Stockmeyer
  • Uzi Vishkin

A complexity theory for unbounded fan-in parallelism is developed where the complexity measure is the simultaneous measure (number of processors, parallel time). Two models of unbounded fan-in parallelism are (1) parallel random access machines that allow simultaneous reading from or writing to the same common memory location, and (2) circuits containing AND's, OR's and NOT's with no bound placed on the fan-in of gates. It is shown that these models can simulate one another with the number of processors preserved to within a polynomial and parallel time preserved to within a constant factor. Reducibilities that preserve the measure in this sense are defined and several reducibilities and equivalences among problems are given. New upper bounds on the (unbounded fan-in) circuit complexity of symmetric Boolean functions are proved.

Details

FOCS Conference 1980 Conference Paper

Structure and Complexity of Relational Queries

  • Ashok K. Chandra
  • David Harel

This paper is an attempt at laying the foundations for the classification of queries on relational data bases according to their structure and their computational complexity. Using the operations of composition and fixpoints, a Σ-Π hierarchy of height, ω2, called the fixpoint query hierarchy, is defined, and its properties investigated. The hierarchy includes most of the queries considered in the literature including those of Codd and Aho and Ullman. The hierarchy to level ω characterizes the first-order queries, and the levels up to ω are shown to be strict. Sets of queries larger than the fixpoint query hierarchy are obtained by considering the queries computable in polynomial time, queries computable in polynomial space, etc. It is shown that classes of queries defined from such complexity classes behave (with respect to containment) in a manner very similar to the corresponding complexity classes. Also, the set of second-order queries turns out to be the same as the set of queries defined from the polynomialtime hierarchy. Finally, these classes of queries are used to characterize a set of queries defined from language considerations: those expressible in a programming language with only typed (or ranked) relation variables. At the end of the paper is a list of symbols used therein.

Details

FOCS Conference 1978 Conference Paper

Computable Nondeterministic Functions

  • Ashok K. Chandra

Functions computed on nondeterministic machines consist of two parts. The halting part which consists of outputs of halting computations, is, as expected, recursively enumerable. The divergence part, which consists of inputs for which diverging computations are possible, can however be any set in Σ11. Such highly noncomputable sets arise if one admits the "finite delay property". This implies that either we make a significant modification to our notion of "computable" as applied to nondeterministic machine models, or else that we ban the finite delay property for nondeterministic models.

Details

STOC Conference 1977 Conference Paper

Optimal Implementation of Conjunctive Queries in Relational Data Bases

  • Ashok K. Chandra
  • Philip M. Merlin

We define the class of conjunctive queries in relational data bases, and the generalized join operator on relations. The generalized join plays an important part in answering conjunctive queries, and it can be implemented using matrix multiplication. It is shown that while answering conjunctive queries is NP complete (general queries are PSPACE complete), one can find an implementation that is within a constant of optimal. The main lemma used to show this is that each conjunctive query has a unique minimal equivalent query (much like minimal finite automata).

Details

FOCS Conference 1976 Conference Paper

Alternation

  • Ashok K. Chandra
  • Larry J. Stockmeyer

We define alternating Turing Machines which are like nondeterministic Turing Machines, except that existential and universal quantifiers alternate. Alternation links up time and space complexities rather well, in that alternating polynomial time equals deterministic polynomial space, and alternating linear space equals deterministic exponential time. Such considerations lead to a two-person game complete in polynomial time, and other games complete in exponential time. We also find that computability on a parallel processing machine is a rather rugged notion, and present two parallel processing models that are polynomially equivalent in their running times. We also show that while n-state alternating finite automata accept only regular sets that can be accepted by 22n-O(logn) state deterministic automata, alternating pushdown automata accept all languages accepted by Turing machines in deterministic exponential time.

Details

TCS Journal 1976 Journal Article

Approximate algorithms for some generalized knapsack problems

  • Ashok K. Chandra
  • D.S. Hirschberg
  • C.K. Wong

In this paper we construct approximate algorithms for the following problems: integer multiple-choice knapsack problem, binary multiple-choice knapsack problem and multi-dimensional knapsack problem. The main result can be described as follows: for every ε 0 one can construct a polynomial-time algorithm for each of the above problems such that the ratio of the value of the objective function by this algorithm and the optimal value is bounded below by 1 - ε.

Details DOI
v2026.09.13