Curriculum Vitae${\mbox \ae}$

Desh Ranjan

Department of Computer Science
New Mexico State University
Las Cruces, NM 88003-8001, USA
Ph: 505-646-4600
email: dranjan@cs.nmsu.edu
http://www.cs.nmsu.edu/~dranjan

AREAS OF INTEREST

My research and teaching interests are in the general area of theoretical computer science and include foundations of computing, computability, data structures and algorithms, complexity theory, parallel computation, optimization and approximation, and computational biology.
 

EDUCATION

• Ph.D. Computer Science, Cornell University, Ithaca, New York. August, 1992.


Thesis Title: Issues in NP-Optimization and Approximation.
Thesis Advisor: Prof. Juris Hartmanis.
 

• M.S. Computer Science, Cornell University, Ithaca, New York. June 1990. Minor in Mathematics.
• Bachelor of Technology Computer Science, Indian Institute of Technology, Kanpur, India. May 1987. GPA: 4.0.

 

EXPERIENCE

• Associate Profesor, Computer Science, New Mexico State University, since August 1999.
• Assistant Professor, Computer Science, New Mexico State University, August 1993-July 1999.
• Visiting Research Scientist, Max Planck Institut für Informatik, Saarbrücken, Germany. May 15-Aug 15 1994, June 1-Aug 15 1995, June 1-Aug 15 1996, July 10-Aug 15 1998.
• Postdoctoral Fellow, Max Planck Institut für Informatik, Saarbrücken, Germany. August 1992-July 1993.

Postdoctoral Advisor: Prof. Kurt Mehlhorn.
• Research/Teaching Assistant, Department of Computer Science, Cornell University, June 1987-July 1992.

AWARDS

1.

Morrison Award for the best Technical Presentation at the Regional ACM Meeting at Ghost Ranch, New Mexico, Fall 1995.

2.

Matehmatical Sciences Institute Fellowship while in the graduate program in the Computer Science Department at Cornell University.

3.

Sage Graduate Fellowship while in the graduate program in the Computer Science Department at Cornell University.

4.

Award for Excellence in each year of the undergraduate program at Indian Institute of Technology, Kanpur. (This is given only to the very top students)

5.

Given the Excellence Award for obtaining 14th rank nationwide among approximately 100,000 examinees in the entrance examination of the Indian Institutes of Technology(IITs).

6.

National Talent Search Scholarship of India for undergraduate studies (only 150 scholarships awarded each year).

7.

Graduated with honors and 14th position among approximately 800,000 students in state-wide High School Examination in India.

PUBLICATIONS
 

Book Articles

[1]

J. Hartmanis, R. Chang, D. Ranjan and P. Rohatgi. ``Relativization: a Revisionistic Perspective'' in Current Trends in Theoretical Computer Science, edited by G. Rozenberg and A. Salomaa. World Scientific Series in Computer Science 40:537-548, 1993.

[2]

J. Hartmanis, R. Chang, S. Chari, D. Ranjan and P. Rohatgi. ``On IP=PSPACE and Theorems with Narrow Proofs'', in Current Trends in Theoretical Computer Science, edited by G. Rozenberg and A. Salomaa. World Scientific Series in Computer Science 40: 484-493, 1993.

 

Refereed Journal Articles

[3]

D. Ranjan, E. Pontelli and G.Gupta. ``Data Structures for Order-sensitive Predicates in Parallel Non-deterministic Systems'', to appear in Acta Informatica, 2000.

[4]

D. Ranjan, L. Longpré, E. Pontelli and G. Gupta. ``The Temporal Precedence Problem'', to appear in Algorithmica, 2000.

[5]

D. Ranjan, E. Pontelli and G. Gupta. ``On the Complexity of Or-Parallelism'', New Generation Computing 17: 285-307 , 1999.

[6]

E. Pontelli, D. Ranjan, and G. Gupta. ``The Complexity of Late-binding in Dynamic Object-Oriented Languages'', Journal of Functional and Logic Programming, Special Issue 2, selected Papers from the Joint International Symposium PLILP/ALP'98, MIT Press, 1999.

[7]

E. Pontelli, D. Ranjan and G. Gupta. ``Efficient Algorithms for the Temporal Precedence Problem on Pointer Machines'', Information Processing Letters 68: 71-78, 1998.

[8]

F. Harary and D. Ranjan. ``Breaking Symmetry in Complete Graphs by Orienting Edges: Asymptotic Bounds'', Information Processing Letters 67(5): 227-230, 1998.

[9]

D. Dubhashi and D . Ranjan. ``Balls and Bins: A Study in Negative Dependence'', Random Structures and Algorithms 13(2): 99-124, 1998.

[10]

B. Borchert, D. Ranjan and F. Stephan. ``On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions'', Theory of Computing Systems 31(6): 679-693, 1998.

[11]

T. Asano, D. Ranjan, T. Roos, E. Welzl and P. Widmayer. ``Space Filling Curves and Their Use in the Design of Geometric Data Structures'', Theoretical Computer Science 181:3-15, 1997.

[12]

T. Asano, D. Ranjan and T. Roos. ``Digital Halftoning Algorithms based on Optimization Criteria and their Experimental Evaluation'', IEICE Transactions on Fundamentals of Electronics, Communications and Computer Science. Vol.E-79-A No.4 April 1996.

[13]

H. Leung, D. Ranjan, H.J. Hernández, D. Tang and A. Gonzalez. ``A Simple Proof on the Decidability of Equivalence between Recursive and Nonrecursive Datalog Programs'', Information Processing Letters 55: 279-282, 1995.

[14]

R. Chang, B. Chor, O. Goldreich, J. Hartmanis, J. Hastad, D. Ranjan and P. Rohatgi. ``The Random Oracle Hypothesis is False'', Journal of Computer and System Sciences 49(1): 24-39, 1994.

[15]

A. Panconesi and D. Ranjan. ``Quantifiers and Approximation''. Theoretical Computer Science 107(1):145-163, 1993.

[16]

D. Ranjan, S. Chari and P. Rohatgi. ``Improving Known Solutions is Hard'', Computational Complexity 3:168-185, 1993.

[17]

D. Ranjan and D. Rus. ``A Tool for the Analysis of Manipulation'', Information Processing Letters, 45(3):117-121, 1993.

[18]

D. Ranjan, R. Chang and J. Hartmanis. ``Space Bounded Computations: Review and New Separation Results'', Theoretical Computer Science, 80(2):289-302, 1991.

Refereed Conference Articles

[19]

N. Futamura, S. Aluru, D. Ranjan and K. Mehrotra. ``Efficient Algorithms for Protein Solvent Accessible Surface Area'', To be presented at HPC-Asia 2000.

[20]

S. Aluru, D. Ranjan and N. Futamura. ``A Parallel Monte Carlo Algorithm for Protein Accessible Surface Area Computation'', In the proceedings of High Performance Computing (HiPC 1999), 1999.

[21]

E. Pontelli, D. Ranjan, and G. Gupta. ``The Complexity of Late-binding in Dynamic Object-Oriented Languages'', In Proceedings of Programming Languages, Implementations, Logics and Programs (PLILP '98), Springer-Verlag Lecture Notes in Computer Science #1490, 213-229, 1998.

[22]

D. Ranjan, E. Pontelli and G. Gupta. ``On the Complexity of Parallel Implementation of Logic Programs'', In 17^thConference on Foundations of Software Technology and Theoretical Computer Science, 1997, Springer-Verlag Lecture Notes in Computer Science # 1346, 123-137, 1997.

[18]

B. Borchert, D. Ranjan and F. Stephan. `` On the Computational Complexity of some Classical Equivalence Relations on Boolean Functions'', TR96-033, Electronic Colloquium in Computational Complexity 1996. Also see internet website http://www.eccc.uni-trier.de/eccc. rate for the conference is not available.

[23]

H. Hernandez and D. Ranjan. ``Decomposability of Datalog Programs'', Presented at the 3rd International Congress on Computer Science Research (CIICC '96), Tijuana, Mexico, November 1996.

[24]

T. Asano, D. Ranjan, T. Roos, E. Welzl and P. Widmayer. ``Space Filling Curves and their Use in Design of Geometric Data Structures'', In Proceedings of the Second Latin American Symposium on Theoretical Informatics LATIN'95, Lecture Notes in Computer Science #911, 36-48, 1995.

[25]

D.Dubhashi, K.Mehlhorn, D. Ranjan and C.Thiel. ``Searching, Sorting and Randomised Algorithms for Central Elements and Ideal Counting in Posets'', In Foundations of Software Technology and Theoretical Computer Science 13^th Conference, Springer-Verlag Lecture Notes in Computer Science #761, 436-443, 1993.

[26]

S. Chari, D. Ranjan and P. Rohatgi. ``On the Complexity of Incremental Computation'', In Proceedings of the 17^thInternational Symposium on Mathematical Foundations of Computer Science, Springer-Verlag Lecture Notes in Computer Science #629, 172-180, 1992.

[27]

D. Ranjan and P. Rohatgi. ``On Randomized Reductions to Sparse Sets'', In Proceedings of the 7^th IEEE Conference on Structural Complexity Theory, 239-242, 1992.

[28]

D. Ranjan, S. Chari and P. Rohatgi. ``Improving Known Solutions is Hard'', In Proceedings of the 18th International Colloquium on Automata Languages and Programming, Springer-Verlag Lecture Notes in Computer Science #510, 381-392, 1991.

[29]

J. Hartmanis, R. Chang, D. Ranjan and P. Rohatgi. ``Structural Complexity Theory : Recent Surprises'', In Proceedings of the 2nd Workshop on Algorithmic Theory, Springer-Verlag Lecture Notes in Computer Science #447, 1-12, July 1990.

[30]

A. Panconesi and D. Ranjan. ``Quantifiers and Approximation''. In Proceedings of the 22nd IEEE Symposium on Theory of Computation, 446-456, May 1990.Also presented at the Fifth Annual Conference on Structure in Complexity Theory, Barcelona, July 1990.

[31]

D. Ranjan, R. Chang and J. Hartmanis. ``Space Bounded Computations: Review and New Separation Results'', In Proceedings of the 14^th International Symposium on Mathematical Foundations of Computer Science, Springer-Verlag Lecture Notes in Computer Science #379, 49-66, 1989.

 

Articles currently under consideration by journals

[32]

Natsuhiko Futamura, Srinivas Aluru, Desh Ranjan. ``Efficient Parallel Algorithms for Solvent Accessible Surface Area of Proteins''. Submitted to Journal of Parallel and Distributed Systems, 2000.

Unrefereed Publications

[33]

T. Asano, A. Hashegawa, D. Ranjan and T. Roos. ``An Optimal Digital Halftoning Algorithm and Its Experimental Evaluation''. Presented at a workshop held by Special Interest Group on Algorithms by Information Processing Society of Japan. Published as Technical Report 31(5) by the Information Processing Society of Japan.

[34]

D. Dubhashi and D. Ranjan. ``Great(er) Expectations''. Technical Contribution, Basic Research in Computer Science (BRICS) Newsletter, No. 5, July 1996, 11-13, BRICS, Aarhus, Denmark.

[35]

D. Dubhashi and D. Ranjan. ``A General Splitting Lemma''. Technical Contribution, Basic Research in Computer Science (BRICS) Newsletter, No. 3, July 1995, 12-13, BRICS, Aarhus, Denmark.

Unpublished Technical Reports

[36]

D. Dubhashi and D. Ranjan, ``On Positive Influence and Negative Dependence'', Technical Report TR MPI-I-98-018, Max Planck Institut für Informatik, Saarbrücken, Germany.

[37]

E. Pontelli, D. Ranjan and G. Gupta. ``On the Complexity of Parallel Implementation of Logic Programs'', Technical Report NMSU-CSTR-9701, Department of Computer Science, New Mexico State University, January 1997.

[38]

D. Dubhashi, V. Priebe and D. Ranjan. ``Negative Dependence through FKG Inequality'', Technical Report

[39]

D. Dubhashi and D. Ranjan. ``Stochastic Majorization: Exploding Some Myths'', Technical Report MPI-I-94-144, Max Planck Institut für Informatik, Saarbrücken, Germany, August 1994.

[40]

D. Dubhashi and D. Ranjan. ``Some Correlation Inequalities for Probabilistic Analysis of Algorithms''. Technical Report MPI-I-94-143, Max Planck Institut für Informatik, Saarbrücken, Germany, August 1994.

[41]

B. Borchert and D. Ranjan. ``The Circuit Subfunction Relations are Sigma2p-complete''. Technical Report MPI-I-93-121, Max Planck Institut für Informatik, Saarbrücken, Germany, May 1993.

 

COLLABORATIONS AND TALKS

• Gave a talk titled ``Randomness, Computation and Cryptography'', New Mexico State University, Department of Mathematics colloquium in the ``Keeping Secrets Secret'' series, Fall 1997.
• Gave a talk titled ``Efficient Data Structures for Parallel Implementation of Logic Programs''. In Workshop on Complexity following the Symposium on Theory of Computing, El Paso, Texas, May 1997. (joint work with Enrico Pontelli and Gopal Gupta)
• Gave an invited talk titled ``Probabilistic Algorithms and Analyses'' at Simposium Internacional de Informatica y Computacion (SIINCO 96) organized by Instituto Technologico de Chihuahua II, Chihuahua, Mexico on Nov 7, 1996. More than 500 people from industry and academia attended the talk.
• Visited Max Planck Institut für Informatik, Saarbrücken (1992-93, Summer 1994, 95, 96). Collaborated with T. Asano, T. Roos, D. Dubhashi, V. Priebe, K. Mehlhorn, C. Thiel, S. Chaudhuri and others.
• Gave a talk titled ``Two Applications of the FKG Inequality''. Los Alamos National Labs, New Mexico, March 1996.
• Visited Basic Reasearch in Computer Science (BRICS), Aarhus, Denmark (Summer 1995, Summer 96) Gave a talk titled ``A 5/3n-comparison algorithm for comparison of circular strings'' in 1996 and collaborated with Dr. D. Dubhashi.
• ETH Zürich, Switzerland (Summer 1993). Gave a talk titled ``Optimization and approximation in the CounterExample Model'' and collaborated with Dr. T. Roos and Dr. P. Widmayer.
• University of Geneva, Switzerland (June 1993). Gave a talk titled ``Optimization and Approximation'' and collaborated with Prof. Jose Rolim.
• Universität Heidelberg, Germany (October 1992). Gave a talk titled ``Issues in NP-Optimization and Approximation'' and collaborated with Dr. B. Borchert.
• Universität Ulm, Germany (September 1992). Gave a talk titled ``On the Complexity of Incremental Computation''.
• Universitat Politècnica de Catalunya, Barcelona, Spain (Summer 1990).

TEACHING AND ADVISING

Courses Taught

• Computability, Computational Complexity, Data Structures and Algorithms, Analysis of Algorithms, Advanced Algorithms, Automata Theory, Discrete Mathematics, Parallel Algorithms, Pascal Programming, C Programming.

Graduate Student Advising

• Doctoral Advisor for Raj Patil. He graduated in Fall 1996 and is currently working for GE Research.
• External Masters' Thesis Advisor for Tarcisio Maugeri, a visiting student from Italy. He finished his Masters' degree from University of Catania in 1997 and is currently doing doctoral work in Austria.
• Doctoral committee member for Garry Hennigan(dean's rep), Enrico Pontelli, Heather Pfeiffer, Deborah Zarrett (dean's representative), Minzhen Wu(dean's representative), Pedro Marquez and Sudip Seal. Masters' committee member for Wei Guo, Cha He, Xuemin Xu, Wei Xiong, Lei Duan, Rong Cai, Ken Mckeever, Miu Har Hon and Hsiang-Tung Lu.

GRANTS

Funded Proposals

• ``Dynamic Data Structures in Advanced Programming Language Implementation: Theory and Practice'' (PI), National Science Foundation, 2000 - 2003, $215,186.
• ``Dynamic and Irregular Parallelism: Its Management in Symbolic and Scientific Computing'' (co-PI), National Science Foundation Minority Institution Infrastructure grant, 1998 - 2003 (Approximately $1,500,000).
• Department of Education Grant for Graduate Assistants in Areas of National Need (GAANN) (co-PI), 9/1/97 - 8/31/2000, $366,765.
• ``CISE Research Instrumentation: Parallel and Distributed Constraint Programming Systems on Multiprocessor PCs: Implementations and Applications'' (co-PI), National Science Foundation, $37,907.

Pending Proposals

• ``ITR/SW+ACS+IM: Extracting Knowledge from Biological Data: Computational Toola and Techniques for Modeling Genealogies, Molecular Evolution and Morphologhy'' (co-PI), National Science Foundation, 2000-2005, $4,379,360.
• ``An Interdisciplinay Program for Training Students for Computing-oriented Careers in Research And Teaching'' (co-PI), Department Of Education, 2000-2003, $489,000.

 

PROFESSIONAL ACTIVITIES AND SERVICE
 

Refereeing and Reviewing
 

Journals

• Applied MAthematical Letters (1998)
• Journal of Computers Systems and Sciences(95)
• SIAM Journal of Computing(96)
• Information Processing Letters (93,94,95,97)
• Theoretical Informatics and Applications (94)

Conferences

• Symposium on Theoretical Aspects of Computer Science (STACS 93)
• Foundations of Software Technology and Theoretical Computer Science (FSTTCS 94, 95, 96, 97)
• International Colloquium on Automata Languages and Programming (ICALP 98)
• International Logic Programming Symposium (ILPS 97)

Books

• Theory of Computation (Addison-Wesley)
• Parallel Computing - Theory and Practice (McGraw-Hill).

Memberships

• Association of Computing Machinery(ACM)
• Special Interest Group on Algorithms and Computation Theory(SIGACT)
• European Association for Theoretical Computer Science (EATCS)

Voluntary Professional and Community Service

• President of the Las Cruces India Association.
• Served as Coach and Advisor for the NMSU CS Programming Competition teams in 1996 and 1997. In 1996, the team won the ACM regionals and went on to participate in the International Competition in San Jose, CA. In 1997, the team finished second in the regionals just missing out on participating in the finals.
• Involved in developing a radio program that will inform general public about exciting potential of careers in computing and will help attract more students into computer science.
• Served as Judge for statewide New Mexico High School Supercomputing Challenge 1997, 1998, 1999, 2000.
• Served as Judge for Graduate Research EXPO at University of Texas, El Paso, 1996.
• Served as Judge for SouthWestern New Mexico Regionl Science and Engineering Fair, Corbett Center, New Mexico State University, Mar 23, 1996.
• Maintained the WEB pages for the NMSU Badminton Club Spring 1998.

References

• Dr. Juris Hartmanis

Walter R. Read Professor of Engineering
Department of Computer Science
Cornell University
Ithaca, New York 14853, USA
e-mail: jh@cs.cornell.edu
Phone: (607)-255-9208
 
• Dr. Arthur Karshmer

Head, Department of Computer Science
New Mexico State University
Las Cruces, NM 88003, USA
e-mail: arthur@cs.nmsu.edu
Phone: (505)-646-3723
 
• Dr. Lane Hemaspaandra

Professor, Computer Science Department
University of Rochester
Rochester, NY 14627-0226
e-mail: lane@cs.rochester.edu
Phone: (716)-215-1203
 
• Dr. Gopal Gupta

Associate Professor, Department of Computer Science
New Mexico State University
Las Cruces, NM 88003, USA
e-mail: gupta@cs.nmsu.edu
Phone: (505)-646-6236