Historical Projects in Discrete Mathematics and Computer Science (2009)
Janet Barnett, Guram Bezhanishvili, Hing Leung, Jerry Lodder, David Pengelley, Desh Ranjan
A course in discrete mathematics is a relatively recent addition, within the last 30 or 40 years, to the modern American undergraduate curriculum, born out of a need to instruct computer science...
The Circuit Subfunction Relations are Σ p 2-complete (2009)
We show that given two Boolean circuits f and g the following three problems are Σ p 2-complete: (1) Is f a c-subfunction of g, i.e. can one set some of the variables of g to 0 or 1 so that the...
Introduction Counting Triangulations of a Convex Polygon (2008)
problem of counting the number of triangulations of a convex polygon. Euler, one of the most
The Computing Alliance for Hispanic Serving Institutions (2008)
Richard A. Aló, Mohsen Beheshti, John Fern, Ann Quiroz Gates, Desh Ranjan
Institutions (CA-HSI) is a consortium of eight institutions that is committed to increasing the number of Hispanics who earn baccalaureate and advanced degrees in computing. CA-HSI is implementing...
Janet Barnett, Guram Bezhanishvili, Hing Leung, Jerry Lodder, David Pengelley, Inna Pivkina, ...
• Summation of Numerical Powers. The discovery of closed formulas for discrete sums of numerical powers, motivated by application to approximations for solving area and volume problems in calculus,...
A Project in Algorithms based on a Primary Historical Source about Catalan Numbers (2008)
David Pengelley, Desh Ranjan, Karen Villaverde
We discuss a project based on an original source from 1838 by Gabriel Lamé, which was used to teach dynamic programming in an Algorithms and Data Structures course for junior level computer science...
We investigate the relative computational power of three classes of pointer algorithms by comparing time and space usage. These classes include two from Tarjan’s original paper and another class...
Efficient parallel algorithms for solvent accessible surface area of proteins (2008)
Natsuhiko Futamura, Srinivas Aluru, Desh Ranjan, Bhanu Hariharan
We present faster sequential and parallel algorithms for computing the solvent accessible surface area (ASA) of protein molecules. The ASA is computed by finding the exposed surface areas of the...
Detecting Local Symmetry Axis in 3-dimensional Virus Structures (2008)
Jing He, Desh Ranjan, Wen Jiang, Wah Chiu, Michael F. Schmid
This paper presents an efficient computational method to identify a local symmetry axis in 3-dimensional viral structures obtained using electron cryomicroscopy. Local symmetry is frequently observed...
On IP=PSPACE and theorems with narrow proofs (2008)
Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi
It has been shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible...
Complexity Analysis of Late Binding in Dynamic Object-Oriented Languages (2007)
Enrico Pontelli, Desh Ranjan, Gopal Gupta
We study the algorithmic complexity of supporting late binding in dynamic object-oriented programming languages. Dynamic object-oriented languages (such as most Prototype-based languages and systems...
Tetsuo Asano, Desh Ranjan, Thomas Roos
Digital halftoning is a well-known technique in image processing to convert an image having several bits for brightness levels into a binary image consisting only of black and white dots. A great...
On the computational complexity of some classical equivalence relations on boolean functions. (2007)
Janet Barnett, Guram Bezhanishvili, Hing Leung, Jerry Lodder, David Pengelley, Inna Pivkina, ...
• Summation of Numerical Powers. The discovery of closed formulas for discrete sums of numerical powers, motivated by application to approximations for solving area and volume problems in calculus,...
Devdatt Dubhashi, Johan Jonasson, Desh Ranjan
Abstract We study negative dependence properties of a sampling process due to Srinivasan to produce distributions on level sets with given marginals. We give a simple proof that the distribution...
On the Complexity of Or-Parallelism (1999)
Desh Ranjan, Enrico PONTELLI, Gopal GUPTA
We formalize the implementation mechanisms required to support or-parallel execution of logic programs in terms of operations on dynamic data structures. Upper and lower bounds are derived, in terms...
Balls and Bins: a Study in Negative Dependence (1998)
Devdatt Dubhashi, Devdatt Dubhashi, Desh Ranjan, Desh Ranjan
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 publications in the BRICS Report Series. Copies...
On the computational complexity of some classical equivalence relations on boolean functions. (1997)
The Random Oracle Hypothesis is False (1997)
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, ...
The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the...
Richard Chang, Juris Hartmanis, Desh Ranjan, Pankaj Rohatgi
1 Introduction Computational complexity theory studies the quantitative laws which govern computing. It seeks a comprehensive classification of problems by their intrinsic difficulty and an...
Negative dependence through the FKG inequality (1996)
Devdatt Dubhashi, Devdatt Dubhashi, Volker Priebe, Volker Priebe, Im Stadtwald, Desh Ranjan, ...
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 publications in the BRICS Report Series. Copies...
Negative dependence through the FKG inequality (1996)
Devdatt Dubhashi, Volker Priebe, Desh Ranjan
We investigate random variables arising in occupancy problems, and show the variables to be negatively associated, that is, negatively dependent in a strong sense. Our proofs are based on the FKG...
On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions (1996)
Bernd Borchert, Desh Ranjan, Frank Stephan
1 Introduction Bernd Borchert Desh Ranjan Frank Stephan f x ; : : : ; x g x ; : : : ; x f x ; : : : ; x g x ; : : : ; x x y y x On the Computational Complexity of some Classical Equivalence Relations...
On the Computational Complexity of some Classical Equivalence Relations on . . . (1995)
Mathematische Logik, Bernd Borchert, Bernd Borchert, Desh Ranjan, Desh Ranjan, Frank Stephan, ...
2 1 2 3 4 1 2 3 4 x x x x x x x x 1 Introduction equivalent isomorphic Bernd Borchert Desh Ranjan Frank Stephan On the Computational Complexity of some Classical Equivalence Relations on Boolean...
The Random Oracle Hypothesis is False (1994)
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, ...
The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the...
The Random Oracle Hypothesis is False (1994)
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Johan Hastad, Desh Ranjan, ...
The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the...
Issues in NP-Optimization and Approximation (1992)
Optimization or finding the best solution for a problem amongst several possible ones is one of the central themes in computing. In particular, NP-optimization (NPO) problems, examples of which...
Issues in NP-Optimization and Approximation (1992)
Optimization or finding the best solution for a problem amongst several possible ones is one of the central themes in computing. In particular, NP-optimization (NPO) problems, examples of which...
Relativization: A revisionistic retrospective (1992)
Juris Hartmanis, Richard Chang, Suresh Chari, Desh Ranjan, Pankaj Rohatgi
In this column we examine the role of relativization in complexity theory in light of recent non-relativizing results involving interactive protocols. We begin with the twice-told tale of the...
Space Bounded Computations: Review And New Separation Results (1991)
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...
Space bounded computations: Review and new separation results (1991)
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...
Improving Known Solutions is Hard (1990)
Ranjan, Desh, Chari, Suresh, Rohatgi, Pankaj
In this paper, we study the complexity of computing better solutions to optimization problems given other solutions. This is done in the context of the counterexample computation model introduced in...
Improving Known Solutions is Hard (1990)
Ranjan, Desh, Chari, Suresh, Rohatgi, Pankaj
In this paper, we study the complexity of computing better solutions to optimization problems given other solutions. This is done in the context of the counterexample computation model introduced in...
On IP=PSPACE and Theorems with Narrow Proofs (1990)
Hartmanis, Juris, Chang, Richard, Ranjan, Desh, Rohatgi, Pankaj
Very recently, it was shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible...
On IP=PSPACE and Theorems with Narrow Proofs (1990)
Hartmanis, Juris, Chang, Richard, Ranjan, Desh, Rohatgi, Pankaj
Very recently, it was shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible...
Structural Complexity Theory: Recent Surprises (1990)
Hartmanis, Juris, Chang, Richard, Ranjan, Desh, Rohatgi, Pankaj
This paper reviews the impact of some recent results on the research paradigms in structural complexity theory.
Structural Complexity Theory: Recent Surprises (1990)
Hartmanis, Juris, Chang, Richard, Ranjan, Desh, Rohatgi, Pankaj
This paper reviews the impact of some recent results on the research paradigms in structural complexity theory.
On IP = PSPACE and Theorems with Narrow Proofs (1990)
Juris Hartmanis, Richard Chang, Desh Ranjan, Pankaj Rohatgi
It has been shown that the class of languages with interactive proofs, IP, is exactly the class PSPACE. This surprising result elegantly places IP in the standard classification of feasible...
The random oracle hypothesis is false (1990)
Richard Chang, Benny Chor, Oded Goldreich, Juris Hartmanis, Desh Ranjan, Pankaj Rohatgi
The Random Oracle Hypothesis, attributed to Bennett and Gill, essentially states that the relationships between complexity classes which hold for almost all relativized worlds must also hold in the...
Quantifiers and Approximation (1989)
Panconesi, Alessandro, Ranjan, Desh
We investigate the relationship between logical expressibility of NP optimization problems and their approximation properties. First such attempt was made by Papadimitriou and Yannakakis, who defined...
Quantifiers and Approximation (1989)
Panconesi, Alessandro, Ranjan, Desh
We investigate the relationship between logical expressibility of NP optimization problems and their approximation properties. First such attempt was made by Papadimitriou and Yannakakis, who defined...
Space Bounded Computations: Review And New Separation Results (1989)
Hartmanis, Juris, Ranjan, Desh
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...
Space Bounded Computations: Review And New Separation Results (1989)
Hartmanis, Juris, Ranjan, Desh
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...
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 \Theta 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...