Joel I. Seiferas, URCS Professor Emeritus

b. 1947. Massachusetts Institute of Technology Ph.D. 1974, The Pennsylvania State University (Assistant Professor 1974-1979, Associate Professor 1979), University of Rochester (Associate Professor 1979-2016, Chairman 1981-1984)

How can we characterize the structure and complexity of the range of algorithms that solve a fundamental computational problem? What are upper and lower bounds on the computational resources (especially time and space) that are needed, and how do these relate to the capabilities of the computer model being used? What are the right architectures to consider, and what are the best techniques for proving such bounds? These and related questions continue to motivate Joel's interest and research in computer science.

Recent research has involved an information-theoretic lower-bound technique based on descriptional complexity and algorithmically incompressible data. Upper bound work has included algorithms for string matching and text indexing, and counter-intuitive real-time simulations of counters and multihead tapes. Recent research supervision and topics courses have involved circuit complexity, probabilistic automata, on-line load balancing, the geometry of string-edit distances, cryptography and multi-party computation, and parallel string matching.

Research with current students involves lower and upper bounds on redistribution cost for on-line density control, and space-efficient techniques useful in the simulation of probabilistic automata.

Selected Publications

• J. I. Seiferas, ``Machine-Independent Complexity'', in Jan Van Leeuwen (ed.), Handbook of Theoretical Computer Science A: Algorithms and Complexity, 163-186, Elsevier Science Publishers and The MIT Press, 1990.
• J. I. Seiferas and A. R. Meyer, ``Characterization of Realizable Space Complexities'', Annals of Pure and Applied Logic 73, 2 (1 June 1995), 171-190.
• P. F. Dietz, I. I. Macarie, and J. I. Seiferas, ``Bits and Relative Order from Residues, Space Efficiently'', Information Processing Letters 50, 3 (9 May 1994), 123-127.
• P. F. Dietz, J. I. Seiferas, and J. Zhang, ``A Tight Lower Bound for On-line Monotonic List Labeling'', Algorithm Theory -- SWAT '94 (Proceedings of 4th Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 824, Springer-Verlag) (Aarhus, Denmark, July 7, 1994), pp. 131-142.
• R. Paturi, J. I. Seiferas, J. Simon, and R. Newman-Wolfe, ``Milking the Aanderaa Argument'', Information and Computation 88, 1 (September 1990), 88-104.
• T. Jiang, J. I. Seiferas, and P. M. B. Vitanyi, ``Two Heads are Better than Two Tapes'', Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing (Montreal, Quebec, Canada, May 25, 1994), pp. 668--675.

Back to URCS Faculty directory

Back to URCS Home Page