Chairman's Introduction, Stuart Kurtz | Faculty Research Summaries

The Department of Computer Science carries out research in theory of computation, artificial intelligence, logic, logic programming, systems, scientific computing, and numerical analysis. This activity is carried out in Ryerson Laboratory, a 100 year-old building on the main quadrangle of the University.

Theoretical Computer Science investigates fundamental questions about the computing process, such as how many operations are necessary to compute a given function, or how to describe precisely a parallel program. Our faculty have contributed to exciting new developments in this area. Laszlo Babai and Lance Fortnow have done extensive work on "transparent proof", a method for transforming very complicated formal (mathematical) proofs into a form that is very easily checked by computer. Instead having to check each step of the proof, the proof can be transformed mechanically in to a new proof which can be verified (with extremely high probability) by spot checking. The application of these ideas has lead to unexpected results in the nonapproximability of certain combinatorial optimization problems. Ketan Mulmuley has attacked the fundamental question of the power of parallelism in a new way that gives new insights. The question he addressed was whether computationally feasible problems can be solved in parallel using very large numbers of processors in a time which is exponentially smaller than on a single processor. For a restricted model of computation he was able to show that this conjecture is not true.

The Chicago Journal of Theoretical Computer Science, founded primarily by members of the Department, with Michael O'Donnell and Janos Simon taking leadership roles, is published by MIT Press on the Internet. It presents articles in a portable markup language.

The Artificial Intelligence Group has focused much of its energy on The University of Chicago Intelligent Information Laboratory, the Info Lab. The purpose of this lab is to develop tools that can extract needed information from the torrent of data available to us due to the revolution in communications that has taken place in the last few years. Kris Hammond, his students, and his coworkers, have been looking at information navigation for text-based documents. The systems that they have developed allow users to inquire about the location of documents by using queries that are phrased in natural language. Using tools based on analysis of the text, not just the matching of key phrases, allows them much of the time to give the user what he wants instead of what he asked for. They have also made advances in structuring voluminous responses, again using text analysis, so that they are more easily absorbed by humans.

Our systems group includes Michael O'Donnell, who is currently working on the digital modeling of sound; and David Beazley, who is working on automatic generation of interfaces for scripting systems.

Our Scientific Computing/Numerical Analysis group is based on Todd Dupont, Ridgway Scott, and their students and visitors. There is substantial interaction between Computer Science and the Computational and Applied Program (CAMP), the Materials Research Science and Engineering Center (MRSEC), and the Center for Astrophysical Thermonuclear Flashes. The numerical simulation of the development of singularities in the mathematical models of physical systems provides a rich array of challenges for computer science, mathematics and physics. Scott is also a member of the new Institute for Biophysical Dynamics.

Faculty Research Summaries