|
Computer Science
Faculty Research Summaries | Chairman's Introduction
László BabaiI work in the fields of theoretical computer science and discrete mathematics; more specifically in computational complexity theory, algorithms, combinatorics, and finite groups, with an emphasis on the interactions between these fields. Asymptotic questions and probabilistic methods are common features in my work in each of these areas. A very recent example: methods of the complexity theories of Boolean circuits and branching programs have been brought to bear on the analysis of a popular random sampling technique in computational group theory. David BeazleyMy research interests are primarily in the areas of systems and software development tools with an emphasis on scientific and numerical computing applications. I also have general interests in software architecture, parallel computing, and scientific visualization. My recent research has focused on SWIG, a compiler I have developed for integrating existing software written in C and C++ with a variety of high-level scripting languages including Python, Perl, and Tcl/Tk. The marriage of compiled languages with scripting languages has a number of interesting features. First, adding an interpreted environment to C/C++ often makes these programs much more flexible and powerful. Second, scripting languages can serve as a framework for building and assembling software components. Finally, scripting languages tend to simplify hard programming tasks and make developers more productive. The primary difficulty is that SWIG tries to perform language integration without requiring users to write formal interface specifications or make modifications to their original code. Given the idiosyncratic (and sometimes frightening) nature of C/C++ programs, much of the research focuses on effective language integration techniques that work across a wide range of programming languages, programming styles, and systems. In addition, I am interested in extending the language integration techniques used by SWIG to other software component systems such as COBRA and COM as well as providing support for other languages such as Java and Fortran. I have also worked on a number of large-scale scientific simulation systems for massively parallel supercomputers and workstation clusters. One of the biggest problems faced by the users of these systems is the enormous quantity and diversity of data that is generated. Thus, I am interested in the problem of scientific data management and the development of general purpose data management tools for scientists. Todd DupontThe main thrust of my research is the construction, analysis, and evaluation of numerical methods for partial differential equations (PDE's), but I also have had interests in related areas such as the construction of mathematical models for physical and biological systems. Approximate solution of PDE's is frequently computationally expensive, even for problems that are conceptually simple. I have been studying ways of using adaptivity to make some of these calculations more efficient and robust. For time-dependent problems the use of meshes that move smoothly with time can be of significant value in producing high quality solutions to difficult problems. Although a general solution to the question of how to use such meshes has not yet been found, there are many situations that I have looked at with my students in which such procedures can be both effective and simple. The computation of free surface flows is important in several of the projects that I am working on at the moment. These involve the formation of drops under various conditions, modeling of the flow of a fluid over a solid surface, and two fluid flows. Kurt FenstermacherKnowledge has become a critical factor in the success of many kinds of organizations, ranging from elementary schools to global Fortune 500 corporations. Many business experts believe that knowledge is an organization's most valuable asset. Although many people agree on the importance of knowledge, however, there are few tools to aid in capturing and reusing it. My research focuses on designing tools and computer-based environments to facilitate knowledge management. I am working to answer questions such as: How do organizations create knowledge? How does knowledge flow among members of an organization? Can computer systems improve the flow and reuse of information? Related research fields can inform such questions. Information retrieval offers powerful techniques for working with text documents, especially when little is known about the documents. How can knowledge about documents augment such techniques? What information about documents would offer the best improvements in retrieval effectiveness? Research in database systems offers important lessons for working with highly structured information, but can the same techniques be applied to loosely structured documents? In short, I am in interested in the broad connections between organizational learning and information technology. Lance FortnowMy interests lie in computational complexity theory: the study of different theoretical models of computation and their relative power usually restricted in resources such as time and memory. While I have worked in a wide variety of areas in computational complexity, I would like to highlight some current directions: quantum computation and lower bounds. Recent work has shown the surprising power of quantum computing--computation based on quantum mechanics. I am most interested in the theoretical limits of quantum computation. My approach is to treat a quantum computer as any other computational model and ignore the underlying physical system. We have already shown close connections between quantum computation and counting complexity--where we study the number of solutions to various search problems. Lower bounds have remained the mecca of theoretical computer science: how do we show certain problems cannot be solved quickly? We have made little progress on problems of this type. I believe that one could show with current techniques that there are problems with easily verifiable solutions cannot be solved with a small amount of space. I have developed several approaches to this problem, one of which has led to the first nontrivial time-space tradeoffs for boolean formula satisfiability. Ian FosterIn my research, I seek to develop tools and techniques that allow people to use high-performance computing technologies to do qualitatively new things. This involves investigations of parallel and distributed languages, algorithms, and communication; and also focused work on applications. I am particularly interested in using high-performance networking to incorporate remote compute and information resources into local computational environments. Current Projects: Globus: Software infrastructure for high-performance computing in wide-area internet worked environments, including resource location, scheduling, security, data access, and communication. Smart instruments: "Computer in the loop" enhancement of scientific instruments, such as high-brilliance X-ray sources. Computational science: Parallel algorithms and modeling in climate modeling and astrophysics. Petaflops computing: Programming model and systems software issues for future extreme-scale computer systems. Kristian HammondMy research efforts are aimed in two directions case-base planing and knowledge navigation. The first involves the exploration of the use of case libraries and transformation rules in planning and problem solving. My aim is to study the notion that planning is a combination of memory access and modification. Part of this work concerns the use of memory in service of opportunistic planning. The aim is to combine planning-time reasoning about the conditions that constitute opportunities with execution-time strategies for the recognition of those features. This work is embodied in the following projects: - RUNNER: A reactive planner in the domain of "errand running"
that plans from episodic information rather than a rule base of operators. These systems all make use of our model of Actualized Intelligence. This model of reasoning and action is the first attempt at constructing a memory-based architecture for the task of controlling an autonomous agent. Most recently, I have begun development of a new set of software agents designed to manage the flood of data colloquially called, the "information superhighway". This approach takes its lead from case-based technology, in that we building systems that communicate via examples rather than explicit queries or questions. We have developed two sorts of systems within this model: - FIND ME: A example-based system for helping users select between
large numbers of possible options. Stuart A. KurtzMuch of the activity of the cell can be thought of as the storage, duplication, and modification of information, i.e., as computation. Given that the cell computes, can we somehow induce it into computing for us? I have been working on biochemically-inspired computational systems, including Adleman's model of DNA-based computing, and a very different model based on protein synthesis that was developed by Mahaney, Royer, Simon and myself. Other current interests include the mathematical theory of computation, logic, and randomness. Ketan MulmuleyI am working in two areas: (1) Design of fast geometric algorithms using randomization; (2) Lower bounds in complexity theory using algebro-geometric methods. A few years ago I had proved a weaker analogue and implication of the $P\not=NC$ conjecture in a restricted but natural PRAM model without bit operations. Currently I am developing geometric complexity theory, which provides an algebro-geometric approach to fundamental problems in complexity theory. It is based on geometric invariant theory and algebraic geometry of equivariant compactifications of honogeneous spaces. Michael J. O'DonnellI am interested in all types of interaction between computer science and logic, including program verification, automated reasoning, logic programming, and foundational interactions. My latest direction is an investigation of the informational structure of sound. I recently started a project to record and analyze notes from the conventional symphonic instruments, which will provide data for testing ideas on sound structure. My earlier work on equational logic programming is summarized comprehensively in two chapters of the Handbook of Logic in AI and Logic Programming, which appeared last year. I am also investigating the application of realizibility semantics from constructive logic to the design and analysis of error-tolerant logics for automated reasoning. As a side-effect, that research is providing new insights into new intuitive foundations of constructive logic. In the new foundations, a proof is constructively valid if it may be communicated reliably in spite of discrepancies in the proof language. L. Ridgway ScottMy group has been devoted to the development of parallel programming tools and parallel algorithms for scientific computation for many years. One visible outcome of the tools work is the P-language family of programming languages and corresponding compilers. The P-language programming approach eases the task of writing parallel programs that harness massively parallel computers and networks of workstations. Based on the P-language explicitly parallel model for scientific and engineering applications, the PC and Pfortran translators recognize a superset of their respective base languages, C and Fortran77. The additional P-language operators provide a means to refer to non-local data and to express aggregate operations. The same P-language constructs are used on different machines without need for modification. So, to port P-language codes often amounts to little more than a re-compilation with the Pfortran and PC translators, followed by a compilation with the native Fortran and C compilers. A number of well-known computational chemistry programs parallelized with Pfortran are now in production use on massively parallel computers. We are currently advancing our compiler technology for the P-languages in a number of directions. Our first step is to enhance the compilers with sufficient analysis capability to incorporate code generation for situations with very irregular computation, that is, computations for which the execution order is not predictable on different processors, yet ones in which tight coupling among processors is required. Complex optimization algorithms require codes of this type, as well as other application areas. In developing the next generation of P-language compilers, we are using a philosophy that we hope can be extended to solve other problems in compiler development. Currently, development of a compiler for a new generation of computer chips is becoming the rate-limiting step in getting a new chip design to market. The additional complexity of the new chip designs makes the development of compilers more difficult, and advances in compiler development analogous to those in chip design are needed. Our approach with the P-language compilers will be to develop a language of code transformations that will simplify the definition of the compiler and facilitate proofs of correctness of combinations of transformations. We hope to extend this methodology to develop modular compilers for subsets of Fortran and C that can be used effectively to compile large libraries for novel computer architectures. Janos SimonMy main research area is computational complexity -- estimating the amount of resources (such as memory, time, number of algebraic operations, or interprocess communication) that are needed to compute functions. One tries to get good upper bounds by exhibiting efficient algorithms and to develop mathematical methods to prove lower bounds. I am especially interested in lower bound techniques for parallel and for probabilistic models. I am also interested both in the theory and applications of distributed computing, in particular the study of fault tolerant distributed computations. Recently, I have started to study the possibility of using recombinant DNA technology to achieve massively parallel computations. This is joint research with Stuart Kurtz (CS). Finally, as editor of an electronic journal, I have an interest in electronic publishing. Robert I. SoareRobert Soare's main research area is mathematical logic and particularly the theory of computability. The theory of computable function emerged during the 1930's with the primitive recursive functions used in Godel's incompleteness theorem, and then the full definitions by Godel [1934], Turing [1936] and others of computable functions which played a significant role in later development of computing devices. Turing [1939] introduced the notion of an "oracle Turing machine" for defining relative computability of a set A from a set B. Sets are placed into equivalence classes called "degrees" if each is computable from the other, i.e. if they code the same amount of information. Since Post [1944] much work has been done on the structure of these degrees, particularly those containing a set which is computably enumerable (c.e.), namely which can be listed in a computable fashion. The degrees are used to classify problems in mathematics as being solvable or unsolvable, such as Hilbert's 10th problem on Diophantine equations. They are also used to compare the information content of one unsolvable problem in mathematics or computer science to another. For example, the problem of deciding whether a program computes a total function is of strictly greater degree than that of the halting problem. The first part of Soare's work has been on degrees and particularly the c.e. degrees, C. Major questions concern the first order theory and classifying the algebraic structure of C. For example, Slaman and Soare [Annals of Mathematics, 1998] unified and extended virtually all the major results and methods about C over the last thirty years to solve the extension of embeddings problem for C, namely to give an algorithm to decide whether a given finite embedding into C can be extended to a second given embedding. This also gives a decision procedure for a large part of the Sigma_2 theory of C. Soare is working on related problems. The second part of Soare's work is on E, the structure of the c.e. sets. Post [1944] initiated the study of the relationship between the degree of a c.e. set and its structural properties in E. Harrington and Soare [Proc. Nat'l. Acad. Sci., 1991] answered a question of Post by producing an E-definable property which guarantees incompleteness. On the other hand, Harrington and Soare have invented a new method [JAMS, 1996] for generating automorphisms of E. Automorphisms and definable properties tend to work in opposite directions closing the gap of our lack of knowledge. Soare and his students are working on a number of questions about automorphisms and definable properties. The third part deals with computability and its interaction with model theory and algebraic structures. From basic theorems of model theory we know when a given theory has prime or saturated models. For example, when does a computable theory have computable prime or saturated models? Soare has worked with Lachlan on degrees of models of the theory Peano arithmetic, and also for full (true) arithmetic, to decide how such a model differs from a mere uniform upper bound for arithmetic sets. Computability has also played a strong role in effective analyses of algebraic structures. For example, when does a structure have an isomorphic copy in every degree, but no computable copy? Soare and another student are working on such questions. Finally Soare is writing a new book on the theory of computability. His previous book with Springer Verlag, 1987, became the standard reference in mathematics and computer science for computability and computably enumerable sets. That book is now outdated with respect to notation, terminology, and new results. The new book is intended as a replacement, updating the initial chapters, omitting many later chapters and writing ones on new results, and adding chapters on the relation of computability to model theory and to computational complexity in computer science. The new book will be called, "The Theory of Computability and Computably Enumerable Sets." Rick StevensI am interested in the development of innovative tools and techniques that enable computational scientists to solve large-scale problems more effectively on the most advanced high-performance computers. Specifically, my research focuses on three principal areas: collaborative visualization environments, high-performance computer architectures, and performance modeling. In the area of collaborative visualization, I am exploring the use of virtual reality in the visualization of scientific data and processes. My efforts include improving displays, recording, and playback of virtual reality experiences; developing new methods for tracking and control and close coupling with parallel supercomputers; and devising new ways of collaborating in virtual environments. Of particular interest to me is teleimmersion -- strategies for synthesizing networking and multimedia technologies to enhance the development of wide-area wide-area collaborative computational science. In the area of high-performance computers, I am studying approaches to computing at the Petaflops Scale, focusing on analysis, modeling, and simulation tools for these ultra-high-performance computers. I am also particularly interested in algorithm and software for multithreaded computer architectures and for hierarchical processor and memory architectures. In a related area, I am investigating analytic performance models that will help researchers understand the performance relationship between high-performance computer systems and scientific applications. My goal is to enable scientific simulations to achieve the very high performance potential of next-generation computer architectures with deep memory hierarchies.
|
 |
|
Division of the Physical Sciences - 5747 S. Ellis Ave., Chicago, IL 60637 - |