b. 1947. Ph.D. (1974) Massachusetts Institute of Technology. Assistant Professor (74-79), Associate Professor (79); The Pennsylvania State University. Associate Professor (79-present), Department Chair (81-84); University of Rochester.
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.
Back to URCS Home Page