Daniel J. Rosenkrantz Ph.D., Columbia University
Leading Professor Emeritus
djr@cs.albany.edu
Computer Science Department
University at Albany
Albany, NY 12222
(518) 442-4270
(518) 442-5638 (FAX)
Statement of Research
Research interests are in algorithms, database systems, and high-performance computing.

Algorithms interests are in combinatorial optimization and network design, particularly developing approximation methods. Also algorithms for analysis, design, transformation, and optimization of various design objects, including programs, hardware, simulation models, specifications, networks, grammars, etc.

Database systems interests are concurrency control, distributed databases, web databases, and data mining. This involves formalizing appropriate models for the concepts involved, and devising efficient algorithms where possible.

High-performance computing interests are in compiling for distributed architectures and in algorithms for distributed systems.
Awards
Excellence in Research Award, University at Albany, 1991.

Fellow of Association for Computing Machinery.

ACM SIGMOD (Special Interest Group on Management of Data) Contributions Award, 2001.
Selected Publications
P. Chundi and D. J. Rosenkrantz, Efficient Algorithms for Segmentation of Item-Set Time Series, Data Mining and Knowledge Discovery, 17, 3, Dec. 2008, 377-401.
H. Siy, P. Chundi, D. J. Rosenkrantz and M. Subramaniam, A Segmentation-Based Approach for Temporal Analysis of Software Version Repositories, J. Software Maintenance and Evolution: Research and Practice, 20, 3, May-June 2008, 199-222.
C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz, R. E. Stearns and M. Thakur, Predecessor Existence Problems for Finite Discrete Dynamical Systems, Theoretical Computer Science, 386, 1-2, Oct. 2007, 3-37.
C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, Complexity of Reachability Problems for Finite Discrete Dynamical Systems, J. Computer and System Sciences, 72, 8, Dec. 2006, 1317-1345.
D. J. Rosenkrantz, L. R. Mullin and H. B. Hunt III, On Minimizing Materializations of Array-Valued Temporaries, ACM Trans. Programming Languages and Systems, 28, 6, Nov. 2006, 1145-1177.
P. Chundi and D. J. Rosenkrantz, Information Preserving Time Decompositions of Time Stamped Documents, Data Mining and Knowledge Discovery, 13, 1, July 2006, 41-65.
D. J. Rosenkrantz, G. K. Tayi and S. S. Ravi, Obtaining Online Approximations Algorithms for Facility Dispersion from Offline Algorithms, Networks, 47, 4, July 2006, 206-217.
H. B. Hunt III, M. V. Marathe, D. J. Rosenkrantz and R. E. Stearns, Towards a Predictive Computational Complexity Theory for Periodically Specified Problems: A Survey, Computational Complexity and Statistical Physics, A. Percus, G. Istrate, and C. Moore (Editors), Oxford University Press, 2006, 285-318.
P. Chundi, R. Zhang and D. J. Rosenkrantz, Efficient Algorithms for Constructing Time Decompositions of Time Stamped Documents, Proc. Sixteenth Intl. Conf. on Database and Expert Systems Applications (DEXA 2005), Copenhagen, Denmark, Aug. 2005, 514-523.
D. J. Rosenkrantz, S. Goel, S. S. Ravi and J. Gangolly, Structure-Based Resilience Metrics for Service-Oriented Networks, Proc. Fifth European Dependable Computing Conf. (EDCC 05), Budapest, Hungary, April 2005, Lecture Notes in Computer Science, Vol. 3463, Springer, 345-362.
P. Chundi and D. J. Rosenkrantz, On Lossy Time Decompositions of Time Stamped Documents, Proc. Thirteenth Conf. on Information and Knowledge Management (CIKM 2004), Washington, DC, Nov. 2004, 437-445.
G. K. Tayi , D. J. Rosenkrantz and S. S. Ravi, Local Base Station Assignment with Time Intervals in Mobile Computing Environments, European Journal of Operational Research, 157, 2, Sept. 2004, 267-285.
C. L. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, On Some Special Classes of Sequential Dynamical Systems, Annals of Combinatorics, 7, Dec. 2003, 381-408.
C. Barrett, H. B. Hunt III, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, Reachability Problems for Sequential Dynamical Systems with Threshold Functions, Theoretical Computer Science, 295, 1-3, Feb. 2003, 41-64.
H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, Parallel Approximation Schemes for a Class of Planar and Near Planar Combinatorial Optimization Problems, Information and Computation, 173, 1, Feb. 2002, 40-63.
R. Ravi, M. V. Marathe, S. S. Ravi, D. J. Rosenkrantz and H. B. Hunt III, Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems, Algorithmica, 31, 1, May 2001, 58-78.
D. J. Rosenkrantz, L. Yu and S. S. Ravi, Efficient Construction of Minimum Makespan Schedules for Tasks with a Fixed Number of Distinct Execution Times, Algorithmica, 30, 1, Jan. 2001, 83-100.
K. B. Lakshmanan, D. J. Rosenkrantz and S. S. Ravi, Alarm Placement in Systems with Fault Propagation, Theoretical Computer Science, 243, 1-2, July 2000, 269-288.
D. J. Rosenkrantz, G. K. Tayi and S. S. Ravi, Algorithms for Path-Based Placement of Inspection Stations on Networks, INFORMS Journal on Computing, 12, 2, Spring 2000, 136-149.
D. J. Rosenkrantz, G. K. Tayi and S. S. Ravi, Facility Dispersion Problems Under Capacity and Cost Constraints, J. Combinatorial Optimization, 4, 1, March 2000, 7-33.
G. K. Tayi, D. J. Rosenkrantz and S. S. Ravi, Path Problems in Networks with Vector-Valued Edge Weights, Networks, 34, 8, Aug. 1999, 19-35.
R. Narasimhan, D. J. Rosenkrantz and S. S. Ravi, Using Data Flow Information to Obtain Efficient Check Sets for Algorithm-Based Fault Tolerance, Intl. J. Parallel Programming, 27, 4, Aug. 1999, 289-323.
M. V. Marathe, R. Ravi, R. Sundaram, S. S. Ravi, D. J. Rosenkrantz and H. B. Hunt III, Bicriteria Network Design Problems, Journal of Algorithms, 28, 1, July 1998, 142-171.
H. B. Hunt III, M. V. Marathe, V. Radhakrishnan, S. S. Ravi, D. J. Rosenkrantz and R. E. Stearns, NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs, Journal of Algorithms, 26, 2, Feb. 1998, 238-274.
S. O. Krumke, M. V. Marathe, H. Noltemeier, V. Radhakrishnan, S. S. Ravi and D. J. Rosenkrantz, Compact Location Problems, Theoretical Computer Science, 181, 2, July 1997, 379-404.
R. Ravi, R. Sundaram, M. V. Marathe, D. J. Rosenkrantz and S. S. Ravi, Spanning Trees - Short or Small, SIAM Journal on Discrete Mathematics, 9, 2, May 1996, 178-200.
Y. Breitbart, H. B. Hunt III and D. J. Rosenkrantz, On the Size of Binary Decision Diagrams Representing Boolean Functions, Theoretical Computer Science, 145, 1-2, July 1995, 45-69.
D. Gu, D. J. Rosenkrantz and S. S. Ravi, Construction of Check Sets for Algorithm-Based Fault Tolerance, IEEE Trans. Computers, 43, 6, June 1994, 641-650.
L. Yu and D. J. Rosenkrantz, A Linear-Time Scheme for Version Reconstruction, ACM Trans. Programming Languages and Systems, 16, 3, May 1994, 775-797.
D. J. Rosenkrantz and H. B. Hunt III, The Complexity of Processing Hierarchical Specifications, SIAM Journal on Computing, 22, 3, June 1993, 627-649.
D. J. Rosenkrantz and S. S. Ravi, Improved Bounds for Algorithm Based Fault-Tolerance, IEEE Trans. Computers, 42, 5, May 1993, 630-635.
D. Gu, D. J. Rosenkrantz and S. S. Ravi, Determining Performance Measures of Algorithm-Based Fault Tolerant Systems, J. Parallel and Distributed Computing, 18, 1, May 1993, 56-70.
L. Yu and D. J. Rosenkrantz, Ancestor Controlled Submodule Inclusion in Design Databases, IEEE Transactions on Knowledge and Data Engineering, 5, 2, April 1993, 352-362.
L. Yu and D. J. Rosenkrantz, Representability of Design Objects by Ancestor-Controlled Hierarchical Specifications, SIAM Journal on Computing, 21, 5, Oct. 1992, 824-855.
P. J. Bernhard and D. J. Rosenkrantz, An Efficient Method for Representing and Transmitting Message Patterns on Multiprocessor Interconnection Networks, J. Parallel and Distributed Computing, 11, 1, Jan. 1991, 72-85.
D. J. Rosenkrantz and H. B. Hunt III, Efficient Algorithms for Automatic Construction and Compactification of Parsing Grammars, ACM Trans. Programming Languages and Systems, 9, 4, Oct. 1987, 543-566.
H. B. Hunt and D. J. Rosenkrantz, Recursion Schemes and Recursive Programs are Exponentially Hard to Analyze, SIAM Journal on Computing, 15, 3, Aug. 1986, 831-850.
P. A. Bloniarz, H. B. Hunt and D. J. Rosenkrantz, Algebraic Structures with Hard Equivalence and Minimization Problems, J. Assoc. Computing Mach., 31, 4, Oct. 1984, 879-904.
D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis, Consistency and Serializability of Concurrent Database Systems, SIAM Journal on Computing, 13, 3, Aug. 1984, 508-530.
D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis, System Level Concurrency Control for Distributed Database Systems, ACM Trans. Database Systems, 3, 2, June 1978, 178-198.
D. J. Rosenkrantz, R. E. Stearns and P. M. Lewis, An Analysis of Several Heuristics for the Traveling Salesman Problem, SIAM Journal on Computing, 6, 3, Sept. 1977, 563-581.
P. M. Lewis, D. J. Rosenkrantz and R. E. Stearns, Compiler Design Theory, Addison Wesley Publishing Co., 1976.