Computer Science
Chairman's introduction, Stuart Kurtz | Faculty Research Summaries
The Department of Computer Science carries out research in the theory of computation, artificial intelligence, logic, the theory and practice of programming, databases and data mining, scientific computing, and numerical analysis. This activity is primarily carried out in Ryerson Laboratory, a 100 year-old building on the main quadrangle of the University. Our department has recently expanded to include research and office space in Hinds, the Geophysical Sciences building.
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 and graduate students have contributed to exciting new developments in this area. Faculty members, Professor Laszlo Babai and Professor Lance Fortnow together with former graduate students Carsten Lund and Mario Szegedy have done pioneering work on "holographic proofs," a method for transforming very long formal (mathematical) proofs into a form that is easily checked by performing a small number of spot-checks. Should the proof contain an error, the method spreads the error to almost everywhere so that even a few spot-checks are likely to detect it (hence the term "holographic"). The application of holographic proofs has lead to unexpected results that have transformed the seemingly remote field of combinatorial optimization. While it has been known for 30 years that efficient methods cannot find the exact optimal solution to a large class of problems in discrete optimization, as a consequence of the fundamental results on holographic proofs we now know that even an approximate solution cannot be obtained by efficient methods. Professor Ketan Mulmuley has brought powerful geometric methods to bear on fundamental questions of computational complexity. First he used "real agebraic geometry" to demonstrate that the efficient solution of certain central problems of discrete optimization is inherently sequential; even a very large number of parallel processor cannot exponentially reduce the time required for the solution. More recently, Professor Mulmuley embarked on developing an entirely new "geometric complexity theory," based on "complex algebraic geometry," which targets the most difficult central problems of complexity theory, including the famous P versus NP problem. Assistant Professor Eric Vigoda, has studied the mixing rate of finite Markov chains, an example of which is, how many times a deck of cards needs to be shuffled to become "random." Questions of this type are of great interest to statistical mechanics as well as to the theory of computing. Solving a long-standing open problem, Vigoda developed an efficient algorithm to count the approximate number of perfect matchings in a bipartite graph. In a separate development, Vigoda, together with former graduate student Tom Hayes, demonstrated new methods to estimate the mixing rate of certain finite Markov chains arising in statistical mechanics.
Our systems group has increased substantially in size and scope in the last several years. Ian Foster has achieved wide recognition for his leadership in grid computing, a new field concerned with collecting and organizing vast computational resources over wide-area networks. Professor Rick Stevens has been active in the development of systems for collaborative visulization, such as a low-cost visualization "wall" and the access grid. Professor Michael O'Donnell is currently working on the informational structure of sound, aiming toward more effective use of sound as an element of human/computer interfaces. New faculty members Professor Anne Rogers and Assistant Professor Svetlozar Nestorov are working in the related disciplines of databases and datamining, which are concerned with managing and exploiting the massive collections of data that are ever more common in science and business. Nestorov is interested in automatically integrating many heterogeneous, disparate information sources. Anne Rogers' current work focuses on collecting, organizing and processing medical data. Nestorov has an active collaboration with a colleague in the Graduate School of Business, while Rogers is involved in a joint project with the Medical School. In the area of software and programming, Professor David MacQueen and Professor John Reppy work on programming language design, formal semantics, and implementation, and are leaders of the SML/NJ compiler project. Professor John Reppy is also developing Moby, an advanced object-oriented language with roots in ML. Assistant Professor David Beazley is working on automatic generation of interfaces for scripting systems, and his SWIG compiler is widely used to access low-level software libraries from high-level scripting languages. Assistant Professor Robby Findler's interests are in formal methods of software design, and in particular contracts, or dynamically enforced interface specifications. He is also a major contributor to the widely-used Dr Scheme system.
The field of artificial intelligence deals with understanding reasoning, learning, language, and perception from a computational perspective, and developing computer systems that exhibit aspects of intelligent behavior. In this area, Associate Professor Partha Niyogi and Professor Yali Amit are applying statistical learning theory to problems in speech, vision, and language. Professor Yali Amit's research concerns development of models and algorithms for visual and acoustic signals. Associate Professor Partha Niyogi is applying learning theory to speech and auditory pattern recognition and language acquisition, and in the process developing new theoretical results in learning theory. Assistant Professor Gina Levow works on natural language processing, spoken language systems, and human-computer interfaces. The department's efforts in natural language and computational linguistics were boosted recently when Professor John Goldsmith from the Department of Linguistics accepted a joint appointment with Computer Science. His interests include unsupervised learning of grammatical structure using machine learning techniques.
Our Scientific Computing/Numerical Analysis group includes Professor Todd Dupont, Professor Ridgway Scott, Assistant Professor Robert Kirby, Professor Rick Stevens and their students and visitors. There is substantial interaction between Computer Science and the Computational and Applied Mathematics Program (CAMP), the Materials Research Science and Engineering Center (MRSEC), and the Center for Astrophysical Thermonuclear Flashes. Dupont and Scott were pioneers in the development of the finite element method, the most widely used method for simulating natural phenomena. Together with Kirby, they are automating the simulation process via the FEniCS project. Scott is also currently pursuing topics in bioinformatics as a member of the Institute for Biophysical Dynamics. Dupont is a member of the James Franck Institute. Professor Rick Stevens is studying analysis, modeling, and simulation tools for petaflops scale computers, as well as performance models for high-performance computer systems.
The department has strong connections with the Toyota Technological Institute in Chicago, a new computer science department established in 2002 and associated with the Toyota Technological Institute of Nagoya, Japan. Professors MacQueen and Reppy collaborate with Matthias Blume on the continuing development of the ML programming language, and Associate Professor Niyogi has a major joint project with Field Medalist Stephen Smale on machine learning theory.
Stuart Kurtz, Chairman