Desh Ranjan

LPAR Conference 2005 Conference Paper

Computational Issues in Exploiting Dependent And-Parallelism in Logic Programming: Leftness Detection in Dynamic Search Trees

• Yao Wu
• Enrico Pontelli
• Desh Ranjan

Abstract We present efficient Pure Pointer Machine (PPM) algorithms to test for “leftness” in dynamic search trees and related problems. In particular, we show that the problem of testing if a node x is in the leftmost branch of the subtree rooted in node y, in a dynamic tree that grows and shrinks at the leaves, can be solved on PPMs in worst-case O ((lg lg n ) 2 ) time per operation in the semi-dynamic case—i. e. ,all the operations that add leaves to the tree are performed before any other operations—where n is the number of operations that affect the structure of the tree. We also show that the problem can be solved on PPMs in amortized O ((lg lg n ) 2 ) time per operation in the fully dynamic case.

TCS Journal 1997 Journal Article

Space-filling curves and their use in the design of geometric data structures

• Tetsuo Asano
• Desh Ranjan
• Thomas Roos
• Emo Welzl
• Peter Widmayer

We are given a two-dimensional square grid of size N × N, where N: =2 n and n⩾0. A space filling curve (SFC) is a numbering of the cells of this grid with numbers from c + 1 to c + N 2, for some c⩾0. We call a SFC recursive (RSFC) if it can be recursively divided into four square RSFCs of equal size. We prove several useful and interesting combinatorial properties of recursive and general SFCs. For an optimality criterion that is important in the design of geometric data structures, we propose a RSFC that is optimal in the worst case and outperforms the previously known RSFCs.

TCS Journal 1993 Journal Article

Quantifiers and approximation

• Alessandro Panconesi
• Desh Ranjan

We investigate the relationship between logical expressibility of NP optimization problems and their approximation properties. First such attempt was made by Papadimitrou and Yannakakis (1988), who defined the class of NPO problems MAX NP. We show that many important optimization problems do not belong to MAX NP and that, in fact, there are problems in P which are not in MAX NP. The problems that we consider fit naturally in a new complexity class that we call MAX Π1. We prove that several natural optimization problems are complete for MAX Π1 under approximation-preserving reductions. All these complete problems are not approximable unless P = NP. This motivates the definition of subclasses of MAX Π1 that only contain problems which are presumably eaiser with respect to approximation. In particular, the class that we call RMAX(2) contains approximable problems and problems like MAX CLIQUE that are not known to be nonapproximable. We prove the MAX CLIQUE and several other optimization problems are complete for RMAX(2). All the complete problems in RMAX(2) share the interesting property that they either are nonapproximable or are approximable to any degree of accuracy.

MFCS Conference 1992 Conference Paper

On the Complexity of Incremental Computation

• Suresh Chari
• Desh Ranjan
• Pankaj Rohatgi

TCS Journal 1991 Journal Article

Space bounded computations: review and new separation results

• Desh Ranjan
• Richard Chang
• Juris Hartmanis

In this paper we review the key results about space bounded complexity classes, discuss the central open problems and outline the prominent proof techniques. We show that, for a slightly modified Turing machine model, low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch's theorem and the Immerman-Szelepcsényi theorem do not hold in the range lg lg n to lg n. We also present other changes in the computation model which bring out and clarify the importance of space constructibility. We conclude by enumerating open problems which arise out of the discussion.

STOC Conference 1990 Conference Paper

Quantifiers and Approximation (Extended Abstract)

• Alessandro Panconesi
• Desh Ranjan

MFCS Conference 1989 Invited Paper

Space Bounded Computations: Review And New Separation Results

• Juris Hartmanis
• Desh Ranjan

Abstract In this paper we review the key results about space bounded complexity classes, discuss the central open problems and outline the relevant proof techniques. We show that, for a slightly modified Turing machine model, the low level deterministic and nondeterministic space bounded complexity classes are different. Furthermore, for this computation model, we show that Savitch and Immerman-Szelepcsényi theorems do not hold in the range lg lg n to lg n. We also discuss some other computation models to bring out and clarify the importance of space constructibility and establish some results about these models. We conclude by enumerating a few open problems which arise out of the discussion.