Arrow Research search

Author name cluster

Krishna V. Palem

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.

8 papers
2 author rows

Possible papers

8

TCS Journal 2024 Journal Article

Energy efficient sorting, selection and searching

  • Varunkumar Jayapaul
  • Seungbum Jo
  • Krishna V. Palem
  • Srinivasa Rao Satti

In this paper, we introduce a model for studying energy efficient algorithms by extending the well-studied comparison model. In our model, the result of a comparison is determined based on two parameters: (i) the energy used to perform a comparison, and (ii) the absolute difference between the two values being compared – thus introducing an energy-accuracy trade-off. This model also extends the ideas presented by Geissmann and Penna [SOFSEM 2018] and Funke et al. [Comput. Geom. 2005] wherein they use two distinct types of comparisons namely low and full-energy (cheap and expensive) comparisons, by introducing multiple types of comparisons. In this extension, the accuracy of a comparison becomes a function of the energy used. We consider the fundamental problems of (i) sorting (ii) selection (iii) searching, and design efficient algorithms for these problems in the new model. We also present lower bounds on the energy usage for some of these problems, showing that some of our algorithms are asymptotically optimal with respect to the energy usage.

Details DOI

FOCS Conference 1994 Conference Paper

Tail Bounds for Occupancy and the Satisfiability Threshold Conjecture

  • Anil Kamath
  • Rajeev Motwani 0001
  • Krishna V. Palem
  • Paul G. Spirakis

The classical occupancy problem is concerned with studying the number of empty bins resulting from a random allocation of m balls to n bins. We provide a series of tail bounds on the distribution of the number of empty bins. These tail bounds should find application in randomized algorithms and probabilistic analysis. Our motivating application is the following well-known conjecture on threshold phenomenon for the satisfiability problem. Consider random 3-SAT formulas with cn clauses over n variables, where each clause is chosen uniformly and independently from the space of all clauses of size 3. It has been conjectured that there is a sharp threshold for satisfiability at c*/spl ap/4. 2. We provide the first non-trivial upper bound on the value of c*, showing that for c>4. 758 a random 3-SAT formula is unsatisfiable with high probability. This result is based on a structural property, possibly of independent interest, whose proof needs several applications of the occupancy tail bounds. >

Details

FOCS Conference 1993 Conference Paper

Highly Efficient Asynchronous Execution of Large-Grained Parallel Programs

  • Yonatan Aumann
  • Zvi M. Kedem
  • Krishna V. Palem
  • Michael O. Rabin

An n-thread parallel program p is large-grained if in every parallel step the computations on each of the threads are complex procedures requiring numerous processor instructions. This practically relevant style of programs differs from PRAM programs in its large granularity and the possibility that within a parallel step the computations on different threads may considerably vary in size. Let M be an n-processor asynchronous parallel system, with no restriction on the degree of asynchrony and without any specialized synchronization mechanisms. It is a challenging theoretical as well as practically important problem to ensure correct execution of P on such a parallel machine. Let P be a large-grained program requiring total work W for its execution on a synchronous a-processor parallel system. We present a transformation (compilation) of P into a program C(P) which correctly and efficiently effects the computation of P on the asynchronous machine M. Under moderate assumptions on the granularity of threads and the size of the program variables, execution of C(P) requires just O(Wlog* n) expected total work, and the memory space overhead is a small multiplicative constant. >

Details

TCS Journal 1992 Journal Article

Optimal parallel algorithms for forest and term matching

  • Zvi M. Kedem
  • Krishna V. Palem

Forest matching is a fundamental step in solving various problems defined on terms such as term matching. We describe the first optimal speedup parallel algorithm for solving the forest matching problem. Our algorithm runs in time O(log n) using n log n processors on a CRCW PRAM, given a forest of n nodes as input. We use this algorithm to design the first optimal speedup parallel algorithm for solving the term matching problem. We also extend these algorithms to run on the weaker CREW PRAM with optimal speedup as well. This will involve a simple randomization scheme for simulating concurrent writes through a use of hashing.

Details DOI
v2026.09.13