FACULTY RESEARCH GUIDE 1998-99 Computer Science Department Carnegie Mellon University 5000 Forbes Avenue Pittsburgh, PA 15213 (412) 268-2565

This file presents the current research interests of the faculty members of the Carnegie Mellon Doctoral Program in Computer Science, along with those of associated faculty of other departments. Each person listed has written his or her own section of the Guide. There has been no attempt to eliminate redundancy by combining descriptions of related work. In addition to the research descriptions, indices at the end of the file list the faculty by interest keywords, and by project names.

The primary purpose of the Guide is to acquaint new and prospective members of our community, especially graduate students, with the on-going research and with the faculty involved. We also use the Guide to inform outside colleagues and visitors, and to direct those looking for someone knowledgeable about any particular topic.

My research is involved with two enterprises. The first is the development of the ACT theory of human cognition. This theory involves a production system architecture which addresses issues of learning, memory, and problem solving. The second is an application of the ACT theory to the development of intelligent tutoring systems for mathematics and computer programming.

My research interests include the integration of machine learning and computer vision, mechanisms for selective attention in vision, artificial neural networks and their applications, and high-dimensional optimization. Currently, I am exploring projects in video indexing, including face and object detection algorithms. One of my goals is to use ideas from machine learning, information theory, and statistics to reduce the dimensionality of raw pixel-based inputs to more informative and usable descriptors of the input visual scene. I also have a continuing interest in using automatically learned temporal information in video sequences to guide processing. Previous work along these lines includes creating and using expectations to guide the NAVLAB autonomous vehicle. Some of the same ideas from information theory that are used for dimensionality reduction in vision can be applied to the optimization of high dimensional functions. Given a function with many parameters, it would be desirable to automatically concentrate effort on tuning the set of parameters which have the largest impact on the optimization. Techniques such as genetic algorithms attempt to do this implicitly; I am working on statistical techniques to make this process explicit by creating probabilistic models of the search space.

The primary research interest of our group (the SCandAL group) is to greatly simplify the task of programming parallel computers. The ultimate goal is to make programming parallel machines as easy as programming sequential machines. Our research involves language, compiler and algorithm development, and considers both theoretical and pragmatic issues. Since parallel computing is still relatively nascent, we believe that working across all these areas is very important for making progress. For example, to generate good parallel algorithms it is important to understand the various limitations of parallel architectures. Similarly, to generate a good parallel language it is important to understand the requirements of parallel algorithms and applications.

Parallel Languages.
Our main interest is programming languages is in determining how parallel algorithms and applications should be expressed in a programming language. There are many different parallel programming styles that have been suggested, and we are interested in the implications of the different styles. In our work we put a strong emphasis on allowing algorithms to be expressed in a clean and concise manner while still supplying a well defined performance model. There is a careful tradeoff between having a language be too high level so that the performance implications are obscured from the user, and having it be too low level such that the programs themselves are obscure.

With these goals in mind we have designed a parallel language called NESL, and have implemented it on several parallel machines, including the Cray C90, Connection Machine CM-5, IBM SP-2, and Intel Paragon. The language allows for a very concise description of algorithms, often as short as the description of the analogous sequential algorithms, and achieves good performance (within a factor of 2 of optimized machine specific code) for many algorithms. There is still a lot of research, however, both in improving the language to extend it to a wider class of algorithms and in compiler techniques for getting better performance in general.

Optimized Implementation of Parallel Algorithms.
Our interest in parallel algorithms centers around the design and implementation of parallel algorithms. We consider algorithm design from both a theoretical and pragmatic point of view, and consider what aspects of theoretical algorithms are important for practical implementations. For example we have studied the sorting problem extensively, have compared many different algorithms for the problem, and have improved them for efficiency. Based on this research, we have implemented the fastest existing general-purpose code for sorting integers or floats. Other algorithms we have studied include algorithms for finding the convex-hull of a set of points, for finding the connected-components of a graph, and for solving sparse linear systems.

My main research interests are in computational learning theory, on-line algorithms, and approximation algorithms. I also am working on applying techniques from graph algorithms to planning problems.

Computational Learning Theory. The goals of computational learning theory are to provide a mathematical understanding of the issues involved in getting machines to learn from experience, as well as to provide new analyzable algorithms. One of the questions I am particularly interested in is: under what conditions can one quickly hone in on the most relevant information in a large feature space? What fundamentally is involved in this task? Some simple versions of this question can be viewed as trying to combine a large number of sources of advice that may be available in a learning setting. Other versions of this question have close relations to cryptography. I am also interested in algorithms for active learning --- learning in settings in which one may actively probe the outside environment to gain additional knowledge --- and methods for fruitfully combining both labeled and unlabeled data in a learning task.

On-line algorithms. On-line algorithms involve repeatedly making decisions knowing only one's past history and without knowledge of future events. For instance, what is a good strategy for deciding when to switch lanes in rush-hour traffic? The Metrical Task System problem is a general on-line problem I have been interested in that (at some level) models a number of settings of this form. Roughly, an algorithm must repeatedly decide whether to continue in its current state or to incur a cost to move to a seemingly better state; but, only at the end, in hindsight, can it tell if it really made the best decisions. There are many important open questions in this area, such as how to make good use of partial prior knowledge, and how to use randomization to beat known deterministic approaches.

Approximation algorithms. Many important problems turn out to be NP-hard, implying that it is unlikely there will be algorithms for them that are both efficient and optimal in the worst case. One approach, then, is to find algorithms that produce approximately-optimal solutions. I am interested in a variety of problems of this sort including traveling salesman-like problems, graph coloring problems, and problems in DNA sequencing. For example, an interesting problem from this perspective is the "trick-or-treater's problem": given a weighted graph (a map of a neighborhood) and an integer k (a candy bag of a certain size), find the shortest route that visits at least k vertices (enough different houses to fill the candy bag). Broadly, the key challenges are to understand the approximability of fundamental problems, as well as to better understand the set of fundamental techniques for achieving good approximation guarantees.

Domain Independent Planning. I have recently become interested in applying techniques from graph algorithms to the setting of domain independent planning. Together with Merrick Furst we have developed the Graphplan planner based on this approach, and I have most recently been exploring the extent to which this method can be applied to probabilistic planning settings.

URL: http://www.cs.cmu.edu/~avrim

My main interests concern the mathematical semantics of programming languages. I believe that proper attention to semantic foundations can yield significant benefits in developing techniques for proving properties of programs, in program design, in language design and implementation.

I am particularly interested in developing intensional semantic models, in which one is able to reason both about the correctness and efficiency of programs. This is in contrast to most traditional semantic models, which are extensional and focus on the input-output behavior of programs while abstracting away from computation strategy. I am working mainly on the semantic foundations of parallelism. This work includes the development of axiomatic proof techniques for establishing behavioral properties of parallel systems, design rules for parallel networks that guarantee desirable behavior such as deadlock-freedom, and the design and implementation of programming languages that employ parallelism uniformly and cleanly.

A semantics for a programming language is an assignment of meanings to program terms. For a semantics to be useful it should accurately capture the computational behavior of program terms, at an appropriate level of abstraction.

I believe that major improvements in the formal treatment of program properties can be achieved by paying careful attention to semantics. If we want to reason about a particular behavioral notion (such as partial correctness) we should first define a mathematical model for programs which precisely captures this behavior without being overly complicated. Ideally, we would like a fully abstract semantics: terms should be given the same meaning precisely when the terms would induce identical behavior in all program contexts. The construction of fully abstract models is by no means an easy task, and depends in any case on the underlying notion of behavior.

For modelling and reasoning about certain types of program behavior, such as partial or total correctness, an extensional semantics is satisfactory: the meaning of a program can be chosen to be a (partial) function from initial states to final states, and all details of how the program goes about its computation can be suppressed since all we really need to keep track of is the state transformation that the program induces. However, such a semantics is no use if we want to make comparisons between programs for the same function. In an extensional semantics all sorting programs have the same meaning, whereas we might well want to design a semantics with which we can compare sorting programs with different computation strategies. This motivation leads to a desire for a theory of intensional semantics. In an intensional semantics the meaning of a program is taken to be an algorithm rather than simply a function. An algorithm can be viewed as a function together with a (mathematical representation of a) computation strategy. I have recently developed a category-theoretic approach to the modelling of algorithms, and applied these ideas to the semantics of the lambda calculus. In the resulting semantic model, there is a complete partial order on algorithms and standard operations such as composition, application, and currying are continuous; thus, one may define algorithms recursively and use the standard techniques of denotational semantics (least fixed points) to reason about recursive programs, even at this intensional level. This approach using categories is rather general, and I am exploring several other possible applications.

Semantic principles and insights should be used in the design of new programming languages, to avoid the development of cumbersome languages in which the programmer may have to labor to overcome the syntactic quirks and idiosyncrasies of the programming language in order to express his algorithm as a program. I am particularly interested in designing a language that embodies parallelism uniformly: it ought to be as easy to specify parallel expression evaluation as it is to specify parallel execution of statements, and it ought to be easy to put together the results of parallel activities. The choice of an appropriate set of primitives for such a language should be guided by proper attention to semantic foundations, and I am carrying out research on this topic.

My primary research interest is in formally verifying hardware designs. This interest grew out of earlier work in logic simulation and symbolic circuit analysis. Over the past few years, we have made great progress in formal verification, to the point where industrial hardware designers are making use of our ideas and tools. These tools promise to eliminate the uncertainty that lingers even after extensive evaluation by techniques such as simulation. The recent fiasco with the defective floating point divider in the Intel Pentium has placed formal verification at the forefront in digital hardware research. Industry is showing great interest in our work. Much more research is required in formalizing and generalizing our methodology, as well as in tool development.

During the course of developing hardware verification tools, I have become quite interested in symbolic representations and manipulation of discrete functions. Most tasks performed by a symbolic manipulator require solving NP-hard problems, and hence there are no known algorithms with good guaranteed performance. Instead, this work seeks heuristic methods that give satisfactory performance in practice. Our approach involves representing functions by directed acyclic graphs and applying graph algorithms to perform operations on functions. The results of our work in this area have spread beyond the original application. Our methods are now being applied to such areas as, temporal logic model checking, logic circuit optimization, automated theorem proving, and truth maintenance systems.

In recent years, we have developed techniques that generalize from Boolean functions, representing each bit of data as a separate function, to word-level functions, representing an entire data word as a function. This has lead to a hierarchical methodology for verifying arithmetic circuits such as multipliers and dividers. In fact, Intel has already started using these methods on their floating point units. I also maintain a longstanding interest in parallel computing, particularly in efficient mappings of application programs onto parallel machines. I am particularly interested in applications involve the manipulation of sparse and dynamically changing data structures. Such applications have historically performed poorly on parallel machines, but I believe that the right combination of architecture, programming model, and algorithms could lead to efficient solution techniques.

My research focuses on computational design theory, methods, automation, and practice, emphasizing. the early stages of design. In particular I explore computational representation, generation and optimizing search of the design space. My premise is that computational tools must support a design process modeled by lateral exploration followed by concentrated investigation of one or more good designs. Based on this premise, much of my work has focused on stochastic optimization algorithms as search techniques, and various grammatical representations to model, generate, and move within the design space. The result is a merging between artificial intelligence and operations research, giving a unique approach to addressing the conceptual design problem.

Grammars are able to concisely model large design spaces. In a competitive society, once such a space is created, it must be searched not only to find a feasible solution, but an optimally directed one. Further, solutions obtained from any computer tool are only as good as the model that represented them, namely the set of objectives and constraints. Thus several equally good solutions are desired from which a designer can consider all objectives, including those not articulated in the model, to select the most preferred one. This motivates our shape annealing technique; shape annealing combines shape grammars and simulated annealing for the generation of optimal shape topologies. Based on the initial success of the technique in solving a knapsack-like problem, we have pursued simulated annealing with shape, string, and graph grammars, and probabilistic move sets, for the design of structures, machines, process plans and product layouts. This work bridges the theoretical aspects of form to function reasoning, the general question of topology generation and optimization, and the practical problem of component layout under a variety of constraints.

From the shape annealing/simulated annealing work we have begun to move in new directions, focusing on agent-based design in a changing environment where agents act based on a grammar representation and focusing on the creation of new stochastic optimization techniques with improved properties over simulated annealing. We are also exploring approaches to symbolic optimization for non-monotonic functions by incorporating robustness considerations into the activity analysis method for monotonic symbolic optimization. These efforts help the designer identify regions of the design space in the early stages of design where optimally directed design concepts lie, for further refinement during the later design stages.

My interests span several areas of Artificial Intelligence and Language Technologies. In particular, my current research is focused on machine learning in the context of language processing, including: tracking and detection of new topics and events, extracting key facts from text, corpus-based techniques for machine translation and translingual information retrieval, and content-based text summarization and text mining. I also work on planning, problem-solving, integrated rational-agent architectures, and large-scale data mining.

The following are my current projects; all represent collaborative efforts with graduate students, research staff, and/or faculty colleagues:

The TDT Project (Topic Detection and Tracking) [with Brown, Lafferty, and Yang]
Automated topic-tracking and new-topic detection for textual, audio and video news media, including developing new classifiers trainable with very few positive instances of events or topics to track. Also, unsupervised learning discovery of new topics at different levels of granularity from unlabeled textual data.

The MMR Project (Maximal Marginal Relevance) [with Goldstein]
Combining information novelty with query relevance in Information Retrieval to minimize redundancy. Also, extending MMR for on-demand query-relevant passage extraction document summarization, including producing unifying summaries of topically-related document clusters.

The HPKB Project (High-Performance Knowledge Bases) [with Mitchell]
Extracting knowledge from text (primarily from The Web) in order to build large-scale knowledge-bases on-demand. My part of the project focuses on extraction of entities and relations.

The DIPLOMAT Project [with Frederking, Brown and Hogan]
Multi-engine machine translation for rapid corpus-based development of MT systems among new language pairs. Diplomat includes speech-to-speech MT and well as text-MT. My focus is on generalizing example-based machine translation methods to produce reasonable MT with "minimal" training corpora.

The Multilingual IR Project [with Yang and Brown]
Multiple methods for bridging the language barrier between queries and document collections in IR, including example-based thesauri, translingual pseudo-relevance feedback, generalized vector spaces, and latent semantic indexing.

The KANT Project [with Nyberg and Mitamura]
High-accuracy knowledge-based machine translation in well-defined semantic domains. Unlike other my other text-based projects that are corpus-based and domain independent, KANT is a knowledge-intensive project to optimize performance given semantically delineated domains.

The PRODIGY Project [with Veloso]
PRODIGY is an integrated intelligent system for problem-solving, planning, analogical reasoning and learning that serves as a baseline platform from which to launch various focused machine learning projects. Whereas Veloso carries the bulk of this project, my primary interest is on learning new domains from examples and observation.

My interests are in multimedia interface development and evaluation, digital video libraries, and computer support for situated learning. My current work as part of the Informedia Project leverages from other CMU CS research in image processing, natural language processing, and speech recognition to enable full content search and retrieval from digital video, audio and text libraries.

Given thousands of hours of video and the need to find a relevant ten minute clip, the user should be able to locate the relevant clip without investing hours of viewing time. I contribute to the development of segmentation and abstraction strategies to meet this goal of more efficient information retrieval from multimedia libraries. I also conduct empirical studies evaluating the effects of multimedia abstractions such as filmstrip views and video skims.

The Informedia library system is currently in use at a local high school. I am interested in improving browsing within this system by supplementing the current query interface with information visualization techniques. I am also involved in a follow-up project which will extend the Informedia scope of accessing broadcast quality multimedia materials in a library setting to capturing, integrating and communicating experiences across people, time and space.

My interests span three areas: Programming Systems, Hardware, and Theory. I use the techniques and insights of theoretical computer science to solve problems in programming systems and hardware design that are of practical interest. I have a number of active research projects in these areas that I would be happy to discuss with students. Below are short descriptions of two research projects that I think are particularly exciting.

Hardware and Software Verification.
Logical errors in finite state concurrent systems like sequential circuits and communication protocols are an important problem for computer scientists. They can delay getting a new product on the market or cause the failure of some critical device that is already in use. The most widely used verification method is based on extensive simulation and can easily miss significant errors when the number possible states of the system is very large. Although there has been considerable research on the use of theorem provers, term rewriting systems and proof checkers for verification, these techniques are time consuming and often require a great deal of manual intervention. My group has developed an alternative approach called temporal logic model checking in which specifications are expressed in a propositional temporal logic and an efficient search procedure is used to determine whether or not the specifications are satisfied.

In the fifteen years that have passed since the original algorithm was published, the size of the systems that can be verified by this means has increased dramatically. By developing special programming languages for describing transition systems, it became possible to check examples with several thousand states. This was sufficient to find subtle errors in a number of nontrivial, although relatively small, circuit and protocols designs. Use of boolean decision diagrams (BDDs) led to a major increase in the size of the examples we could handle by this technique. Representing transition relations implicitly using BDDs made it possible to verify examples that would have required 10@^20 states with the original version algorithm. Refinements of the BDD-based techniques have pushed the state count up over 10^100 states. By combining model checking with abstraction, we have been able to check even larger examples. In one case, we were able to verify a pipelined ALU design with 64 registers, each 64 bits wide, and more than 10^1300 reachable states.

Analytica --- A Theorem Prover for Mathematica.
Analytica is an automatic theorem prover for theorems in elementary analysis. The prover runs in the Mathematica environment and is written in Mathematica language. The goal of the project is to use a powerful symbolic computation system to prove theorems that are beyond the scope of previous automatic theorem provers. The theorem prover is also able to guarantee the correctness of certain steps that are made by the symbolic computation system and therefore prevent common errors like division by a expression that could be zero.

Since we wanted to generate proofs that were as similar as possible to proofs constructed by humans, we use a variant of natural deduction to generate proofs. We have demonstrated the power of our theorem prover on several non-trivial examples including the basic properties of the stereographic projection and a series of three lemmas that lead to a proof of Weierstrass's example of a continuous nowhere differentiable function. Each of the lemmas in the latter example is proved completely automatically. In a related project that uses similar techniques, we have managed to prove all of the theorems and examples in Chapter 2 of Ramanujan's Collected Works completely automatically. We believe these examples provide convincing justification for combining powerful symbolic computation techniques with theorem provers.

I am interested in image understanding and computer vision systems, especially in the area of binocular stereo from passively-acquired imagery. I am currently working with Dave McKeown and Chris McGlone in the investigation of the automated analysis of aerial imagery to support research in computer vision for digital mapping.

Binocular Stereo.
Humans are able to surmise depth in 2-D "monocular" images and to perceive it through the stereoscopic fusion of a pair of images. The process used by the human visual system to achieve this, however, is not well understood. How, then can we produce autonomous systems which are able to extract depth information about, and interact with, their environments? One way is to attempt to simulate some of those processes, which seem to be present in the human visual system, and learn what does and does not work. This approach allows us to attempt automatic visual recognition of objects, and, perhaps in some cases, to gain insight about the operation of the human visual system. The perception of depth from a stereo pair provides both a qualitative and a quantitative measure in depth determination that is not available from a monocular view and produces the ability to detect objects which are difficult to distinguish from the background due to similar image intensities or textures. For my theses work at USC, I developed a Stereo Vision System (SVS) in which I showed methods to integrate primitives derived from area-based and feature-based stereo matching algorithms. I have continued this work at CMU particularly with respect to improvements in stereo matching accuracy and refinement.

Aerial Image Analysis and Automated Cartography. One goal of automated cartography is to generate an accurate 3-D model, or map, of a geographic region that includes the delineation and labeling of natural and man-made structures. Beginning with multi-spectral/multi-viewpoint aerial imagery we are investigating the development of cooperative methods for stereo analysis using area-based and feature-based methods and the fusion of monocular cues for building extraction.

My interests are in the application of artificial intelligence to education, in particular, the use of cognitive models in computer-based tutoring environments. Our approach is to build tutoring programs around rule-based models of how people perform skills, such as programming. Such a model allows the tutoring program to solve practice exercises along with the student, providing help as needed. My research has focused recently on estimating students' mastery of the knowledge represented in the cognitive model. By integrating learning and performance assumptions with the cognitive rules, we attempt to predict students' test performance, shape practice appropriately and improve the model. I am also interested in related issues in the design of computer-based practice environments, for example the content and timing of help messages and their impact on students' performance.

My work is focused on various aspects of computer music, a field which poses many challenges for computer science. I also direct the Just-In-Time Lecture Consortium, which offers a new technology for low-cost, computer-based training and education.

A central problem in computer music is expressive control, that is, the detailed control of timing, gesture, nuance, and tone quality that is essential to music. This problem has many facets, resulting in a variety of research directions. The Computer Music Project has developed new languages, development tools for real-time systems, synthesis techniques, and music understanding systems. This research is more than intrinsically interesting. It can shed light on related problems in real-time systems, multimedia, human-computer interaction, and artificial intelligence. Moreover, new possibilities of control and interaction in music are changing the very nature of music composition, performance, and aesthetics.

One research example is the the development of new languages for expressing temporal behavior. One of these is Nyquist, a language that provides a single abstraction mechanism for the seemingly different notions of ``note,'' ``instrument,'' and ``musical score.'' Nyquist gives composers an elegant, uniform notation that spans the range from low-level digital signal processing to high-level music composition. At present, Nyquist does not generate sound in real-time, but as processors increase in speed, software for sound synthesis will replace special-purpose hardware synthesizers. Nyquist already provides one of the fastest sound synthesis implementations, and a future version will support real-time synthesis.

Expressive control of musical tones is another topic of research. A violin is expressive because there are many parameters under continuous control by the player, including bow pressure, finger and bow positions, and bow velocity. These give rise to variations in the resulting sound. My colleagues and I have developed a new synthesis technique, spectral interpolation, which allows us to synthesize tones with interesting variations in spectra. Spectral interpolation has been used to accurately synthesize a variety of instruments. In the future, we will use this technique to give composers and performers greater intuitive control over synthesized sound.

Real-time performance systems present interesting problems. I have developed several systems for real-time music understanding that ``listen'' to a live performance and derive some abstract information regarding rhythm, tempo, harmony, etc. The degree of understanding is usually demonstrated by having the system participate in the performance. One example is Computer Accompaniment, in which the computer follows a performance in a score and plays an accompaniment in synchronization with the performer. My computer accompaniment technology appeared in a commercial product in 1994. Another example is a system that listens to an improvisor playing 12-bar blues and plays the part of a rhythm section. Systems that perform both of these tasks have been built here, but this is only the beginning of what is possible. Current work includes more sophisticated systems for listening to improvisations, ensembles, and vocalists.

Education is another interest. Our country spends more for education than for health care, and as with health care, education costs are growing faster than the inflation rate. Computer-based tutoring systems have much to offer, but development costs and lack of expertise have made it difficult to produce good tutoring systems. Work on automating instructional design principles to lower the cost of intelligent tutoring systems led to an even simpler approach, ``Just-In-Time Lectures,'' in which presentations are captured using digital video, synchronized slides, a table-of-contents, and links to the Web. Just-In-Time Lectures have been used to deliver entire courses and by large corporations for training.

I am interested in making robots act purposefully and successfully in a world in which most everything is uncertain. Sensory information is inaccurate or noisy, actions seldom have a precise effect, and objects in the world are often in the wrong location or orientation. Despite such obstacles to purposeful action, there are many tasks that can be accomplished successfully. Humans, animals, and some machines are proof. Providing robots with the ability to operate autonomously and purposefully requires an understanding of how different tasks may be accomplished by different repertoires of actions. Grasping, hitting, and dropping are some actions that are useful in a robot's repertoire. More exotic actions include shaking, twirling, and other actions that randomize an object's state. My current work focuses on two-palm manipulation, in which two arms cooperate to manipulate objects dynamically, that is, without the need for full kinematic constraint. My work is motivated by several desires. First, I would like to program robots more easily than is currently possible. Second, I would like to understand the scope and limitations of autonomous systems, whether biological or artificial. Third, I would like to reduce the complexity of design and planning by codifying the design parameters required to achieve a given level of automation. An underlying goal of my research is to understand the relationship between sensing, action, and prediction. In the past, I have explored various extreme points in this space. With Matt Mason I explored sensorless strategies, for my thesis work I looked at randomized strategies, and most recently I investigated fast-action minimal-sensing strategies. My research draws on tools from geometry, mechanics, planning, and probability.

AI AND MACHINE LEARNING:
For most of my career I have been exploring the idea that recognition and other essential operations of human intelligence may depend on the use of massively parallel computation rather than clever algorithms and data structures. Instead of using a single processor to look at data sitting passively in memory, we need some kind of active memory in which all of the available knowledge participates in producing a response. My first experiments in this area led to the NETL system, essentially a semantic network with a very simple computing element permanently assigned to each node and link in the network. In recent years, I have become interested in more neuron-like architectures that represent knowledge in a distributed form and that can learn new behaviors from examples.

My students and I have developed several improved learning algorithms for neural networks, including Quickprop, Cascade-Correlation, and several variations on these. Cascade-correlation is very fast, scales up well, and it constructs a network of the appropriate size and shape as it works on a problem. These algorithms are being used in a large number of application projects worldwide.

Most current learning algorithms employ "supervised" learning: the system is trained by showing it a collection of input/output pairs illustrating the desired behavior. However, in many domains, such labeled training data is scarce. I am currently interested in developing better algorithms for "unsupervised" and "partially unsupervised" learning, in which the learning algorithm must discover interesting and useful structure in an unlabeled stream of experiences.

THE GWYDION PROJECT.
Most of software engineering is concerned with producing a program that meets a pre-existing specification. I am more interested in tools for "evolutionary" or "incremental" programming, in which the programmer doesn't know what he really wants until after program is running. This kind of programming puts a premium on fast prototyping and the ease of making changes. Languages like Common Lisp and Smalltalk have always been excellent vehicles for this kind of programming, but they have paid a price in the size and speed of the delivered application program. This has limited the use of these languages in "mainstream" programming.

The Gwydion Project (named for character in Welsh mythology) is developing a programming environment based on the idea of "hypercode", whose goal is to retain all kinds of knowledge about a software system: code, comments, requirements, design rationale, edit history, testing history, and so on. This information is linked together and to the code in a manner analogous to hypertext. A collection of powerful and flexible tools is provided for navigating and editing this rich texture of information. The Gwydion project originally focused on Dylan, a Lisp-like language with better delivery characteristics. Recently, we switched to Java, which (for now) enjoys much greater popularity in industry.

JUST RESEARCH.
I am currently on half-time leave of absence from the CMU faculty so that I can head Just Research, a new computer science research center located a few blocks from CMU. This laboratory was established by Justsystem, a large software company based in Tokushima, Japan. Just Research conducts research in many areas, including information retrieval, natural language processing, image processing, and machine learning applied to all of the above. The lab maintains close ties to the CMU community. Many of our Ph.D.-level researchers have adjunct faculty appointments in SCS, and we have employed a number of CMU students in part-time and summer positions.

The first project examines fast methods for approximate matching in multimedia databases. Typical queries are as follows: "in a collection of product photographs, find pro- ducts that look like tennis shoes"; "in a collection of med- ical X-rays, find ones that look like the X-ray of the current patient, and list the corresponding diagnoses". The main idea behind our approach is to extract n features from the objects of interest (typically, with the help of a domain expert), thus mapping each object into a point in n-dimensional feature space. Subsequently, we can use state-of-the-art database techniques (like the 'R-trees') to store and retrieve these $n$-dimensional points. The philo- sophy of our approach is to provide a the vast majority of irrelevant objects. Allowing some 'false alarms' is accept- able, because they can be easily discarded by a elaborate test, or even by the user. We have already successful sets of features for 2-d color images, 2-d shapes, and 1-d time series (such as stock-price movements). Depending on the domain, we are experimenting with modern signal processing techniques, such as the discrete wavelet transform for sound and images, hidden Mar- kov chains for digitized voice, the discrete cosine transform for stock-price time series.

The second project focuses on data mining. The goal is to discover correlations ('rules') in a collection of records. For example, in a set of patient records with demographic characteristics, symp- toms and diagnoses, we would like to find all the 'interest- ing' rules (eg., 'patients >50 years old with cholesterol >300 have 10% probability of heart attack'). We are studying traditional clustering methods as well as statistical methods like the 'Singular Value Decomposi- tion' (SVD), to do cluster analysis and rule discovery.

The last project examines algorithms and architectures for fast execution of expensive database operations. We are working on Active Disks for data mining, on striping and placement algorithms for video servers, and on buffering algorithms for database operations.

My main research interests are the theory, design and implementation of high performance information systems. The general theme of my work is to understand and exploit the interplay of applications and new technologies. At various times this work has involved designing parallel algorithms, parallel architectures, custom chips, and specialized compilers. My current activity centers on the architecture and control of high speed networks as infrastructure for communication and for parallel computation. Colleagues and I have recently completed the Credit Net project, which has designed and is in the deployed a 622 megabit-per-second ATM local area network. I am currently working with Peter Steenkiste, Hui Zhang and our students and staff on the Darwin project, which involves the design of algorithms to allocate and control resources in the network, and of interfaces and software to support applications in parallel computing and multiparty, multimedia communication. The overall goal of Darwin is to develop the infrastructure need to provide dynamic electronic service creation and deployment in future networks.

I am interested in internet-based tools for resource discovery and information exchange. Research is underway developing distributed information exchanges. The net provides opportunities for new kinds of information markets and mechanisms of exchange that are far from understood. The rapid emergence of these new mechanisms itself provides a market to think about. As I work in this area I am becoming increasingl interested in fundamental architectural issues relating to the design of efficient RDBMS-backed web sites. I spend a great deal of time tracking new web-based phenomena and trying to invent technologies that can be at the crossroads of internet commerce-based traffic.

Until a few years ago I spent a lot of time establishing connections between computer science and mathematics with the goal of developing new computational tools and methods. I worked on discovering new algorithms and understanding the inherent complexity of fundamental computational problems. I also worked on graph-theoretic algorithms, problems in circuit and algebraic complexity, applications to parallel computation and theoretical aspects of machine learning theory.

In complexity theory I mainly worked on the complexity of representing functions as circuits. This approach held the most promise, of all known approaches, for resolving the P versus NP problem. In this work many beautiful mathematical methods are employed, for example: the combinatorics of probabilistic restrictions, counting arguments, algebraic decompositions, geometric arguments and communication complexity. I am less active in this area but remain curious about outcomes.

A couple of years ago Avrim Blum and I created a new representation of plans. This new representation, which we call Planning Graphs, reorganizes many classical exponential AI searches for STRIPS-like plans and makes them manageable. The implementations to-date show great promise and are getting a lot of attention in the AI planning community. There are many possible extensions which seem plausibly practical for real-world applications and I would be interested to explore these further.

I have broad research interests in computer systems, including operating systems, networking, storage systems, computer architecture, performance evaluation, and distributed systems. I am particularly interested in developing new ways of structuring computer systems (hardware and/or software) to address technology changes and enable new applications. One place where I see an opportunity for large, fundamental changes is in the ongoing shift in importance from conventional computing to I/O and data movement -- we need computer system designs that treat I/O components as first-class entities, allowing them to actively and adaptively cooperate in the completion of useful work.

My students and I are currently pursuing several topics of research:

* design and implementation of extensible I/O software.
* design and implementation of application-level networking.
* construction of high-performance network servers
* implementation and use of application-controlled storage management
* improved general-purpose file system support for small file I/O

My field of interest is software engineering, and specifically the areas of applied formal methods, software architectures, and software development environments. The common thread that links these areas is the problem of controlling the complexity of large software systems by providing a scientific basis for software design.

Applied Formal Methods.
The traditional use of formal (or mathematically-based) methods has been to solve the problem of refinement: given a formal specification of a system, how does one construct an implementation that is correct with respect to that specification. In contrast, my interest in formal methods is in dealing with the inverse problem of abstraction: given a family of existing systems, how does one construct a formal model that characterizes the important commonalities in these systems. When used in this way, formal methods become a tool for extracting reusable software architectures, for clarifying system design, for simplifying the way we think about a class of system, and for building a framework for reuse. Among the important research issues are those of methodology (How should we use formal notations in practice to arrive at system abstractions?), language (What notations, type systems, parameterization mechanisms, etc. are best suited to this use of formal methods?), and reusability (What properties of a formal model best support reusability, evolution, and adaptation?).

Software Architecture.
Successful design of software architecture has always been a major factor in determining the success of a software system. But until recently architectural design has been largely based on ad hoc choice, informal experience, and local expertise. The goal of this research is make this knowledge precise, codified, and available to engineers as a matter of routine engineering. An example of where this has been successfully accomplished is compiler construction: what once took years to develop is now done routinely by undergraduates in a semester course. This is because compiler development is based on a well-defined, formalized software architecture, which defines a set of abstractions that give the software engineer a conceptual grasp of the problem, leads to a focused set of tasks that must be performed to specialize the architecture for a specific compiler (lexical analysis, parsing, flow analysis, etc.), and enables automated support for the compiler construction tools (parser generators, attribute evaluators, etc).

The goal of this research is to demonstrate that similar architectures can be obtained for other classes of software. In particular, the design abstractions obtained through the application of formal methods to the design process (mentioned above) are natural candidates for architectures.

Software Development Environments.
Given a well-defined architecture, it is natural to attempt to support its use with development tools and environments. The ABLE project is currently building a system, called AESOP, for generating environments that support specific classes of architectures -- or architectural styles. Given a description of an architectural style, AESOP produces an open environment for creating software designs in that style, reasoning about properties of those systems, integrating external tools, and graphically visualizing architectural designs. The ABLE project also is developing transformational techniques for specializing general-purpose environments: using these techniques we are able to adapt existing environments so that they support the creation of application-specific programs.

I am interested in computer systems architectures, in particular, memory systems architectures employing prefetching, parallel and video file systems, redundant arrays of disks, high bandwidth networks and workstations and multicomputer operating systems. Towards these goals, I lead the Parallel Data Laboratory (PDL) in the following projects.

Currently, most of our effort is focussed on the Network-Attached Secure Disks (NASD) project. The central goal of NASD is to establish an intelligent storage interface and to develop the distributed and parallel file system technology to exploit it. This new interface features direct communication between clients (possibly cluster servers) and storage devices or subsystems. Direct communication enables cost-effective scalable striped storage, file server offloading and reduced messaging, storage processing and bandwidth proportional to capacity, device-enforced security, and extensible storage intelligence available for application needs (Active Disks). The Lab develops full-function prototype systems and evaluates these against real applications. For example, in the fall of 1998 we are building a 1.25 TB array of 100 NASD (or Active Disk) nodes to be tested with data mining applications (such as association discovery from consumer transactions) and multimedia applications (such as medical image processing and digital library retrieval and viewing). In the spring of 1998, this project branched out to examine the use of intelligent network devices (Active Networks) for storage functions such as caching, redundancy or load balancing. We also participate in a National Storage Industry Consortium (NSIC) industry working group devoted to developing the appropriate interfaces for network-attached storage devices.

Our informed prefetching and caching research (TIP) proactively tailors file system resource management to the needs of I/O-intensive applications. With applications disclosing access patterns, TIP increases I/O concurrency to exploit the full parallelism of disk arrays, fetching further ahead on congested disks as needed. Our implementation is based on an extensible cost-benefit resource allocator and encapsulates within each module bidding for resources all policy related to that module's allocation strategy. Hints, the key to TIP's dramatic reduction in elapsed time (approximately linear in the number of disks for many I/O-intensive applications), can be automatically generated by runtime and compilation means. Both techniques are currently being explored; speculative pre-execution of runtime code stalled waiting for I/O generates probable future reads and compile time loop unrolling predicts a superset of future virtual memory page-ins.

Our Scalable I/O collaboration (SIO) , with Caltech, Rice, Princeton, Arizona, Washington, Argonne, Illinios and others, is focussed on defining and demonstrating extensions to the traditional UNIX file system programmer's interface to portably support high-performance, parallel applications. PDL researchers are implementing the SIO parallel file system API in a cluster of workstations environment employing network-attached secure disks. Designed to operate outside of client operating system kernels while providing dynamically configurable failure tolerance, our parallel file system will fully exploit the features of NASD devices.

The Lab's original and most well-documented project, redundant disk arrays (RAID) , is largely complete. In its heyday we worked on RAID architectures for improved performance in the presence of failures and architectures for reducing the failure-free penalty for maintaining redundant information. More recently, the RAID project developed and published a rapid prototyping framework for RAID systems. This executable framework, RAIDframe, enables us to treat RAID architectures as simple graphical programs amenable to automatic error recovery and rapid modification. RAIDframe efforts persist as local and remote colleagues port and extend RAIDframe.

The Lab is equipped with a few hundred disk drives in various arrays and standalone configurations. About 50 Digital Equipment Alpha workstations with 133 to 500 MHz processors form the basis of the Lab's computing. To these we have recently added 64 300 MHz Pentium II workstations. Networking is provided with a 52-port OC3 ATM switch, a collection of 24-port 100Mbps Ethernet switches and am 8-port 1.28 Gbps Myrinet switch.

The Lab is advised and supported by a consortium of companies including Hewlett-Packard, Intel, Compaq, 3Com, Seagate, Quantum, Clariion, Symbios Logic, StorageTek and Wind River. Representatives of these sponsors visit CMU for at least three days per year to participate in the Lab's annual retreat and workshop, typically in the late fall at an off-campus conference facility nearby CMU.

My research area is computer architecture and compilers. Currently my interest is focused on novel ways to use the hundreds of millions to billions of transistors that will be available to processor designers in the near future. In particular, I am interested in how user programs written in high-level languages can be compiled directly into hardware, yielding order of magnitude speedups.

The key architectural feature that enables huge speedups is the reconfigurable fabric (similar in concept to today's FPGAs), which can be configured to any hardware circuit. The reconfigurable fabric is then integrated with a simple super-scalar processor core, resulting in a high-powered general-purpose processor. The compiler for such a system partitions a program into sections that are executed either on the core or on the reconfigurable fabric. It synthesizes communication and synchronization code and also creates the hardware configurations.

The research is proceeding on four fronts: (1) the development of techniques for compiling high-level languages to reconfigurable fabrics, (2) the design of Tiger, a TIghtly coupled General-purpose processor with a Reconfigurable fabric, (3) The design and implementation of PipeRench, a compiler-friendly computation-based reconfigurable fabric, and (4) the creation of a benchmark suite workload 2000.

The compilation technology we are developing allows users to program Tiger processors in high-level languages without requiring them to understand the actual implementation details of the reconfigurable fabric or the processor/fabric interface. We have already completed our first version of a compiler that creates configurations for fabrics from a text-based dataflow intermediate language (DIL). We are now investigating techniques to turn C programs into executables for Tiger machines. Among other things, we are investigating how to automatically partition a C program between the general-purpose core and the reconfigurable fabric, how to create hardware pipelines from C code, how to retime circuits to reduce register pressure, and how to speed up place-and-route without compromising efficiency.

As part of this research effort I am collaborating on the design of a new reconfigurable fabric called PipeRench. PipeRench is the first FPGA-like device that virtualizes the physical array allowing designs larger than the physical device to run efficiently. Furthermore, unlike previous FPGAs, PipeRench is oriented toward the implementation of data paths instead of random logic. We expect to fabricate PipeRench in late 1998. Currently, using our DIL compiler, we have implemented many kernels on PipeRench and have, at least initially, validated our assumption that PipeRench's compiler-friendly design enables our goal of compiling high-level languages automatically to the fabric.

My other areas of interest are parallel object-oriented languages and fine-grained parallelism.

Areas: (I have included all areas, including the ones I am currently listed under in this list. Also note that reconfigurable computing new areas)

My research interests center on how to build (design, program, implement) systems. "Systems" in this context refers to a software system executing on some hardware platform. One of the challenges in system design is to develop good abstractions and tools (both for the software and hardware side) to simplify the task of building the system. Therefore, my research includes the building of tools (often compilers) to support system development.

I'm involved in two projects: one (Fx) focusses on the mapping of programs onto parallel and distributed systems; the other (cmcc -- for CMU's C Compiler) investigates the construction of an optimizing C compiler.

Together with other researchers (both inside the School of Computer Science and in other departments), I work on developing applications, usage models, abstractions, and programming tools for scalable computers. This class of platforms includes networked workstation clusters (or "networks of workstations", although these networks in practice include a lot more than workstations) as well as parallel systems. The core of our effort is the Fx compiler, which maps application programs written in a dialect of High Performance Fortran (HPF) onto a variety of systems. The Fx compiler system has been (re)targeted at the Cray T3D, the Intel Paragon and iWarp, and the Nectar Gigabit Testbed. Efforts to target new ATM-based networks like CreditNet are under way. The Fx compiler provides a unique framework to explore issues in parallel computing, ranging from applications to computer architecture. For example our input language allows the user to pass hints about the alignment and distribution of data objects (i.e., how the elements of an array are to be placed relative to other arrays and relative to other elements of the same array). These directives guide the compiler when mapping applications with access patterns that are too hard for a compiler to analyze.

HPF and its dialects form one class of languages that can be used for the programming, and HPF has demonstrated some success for the programming of "regular" problems. (A problem is called "regular" when the distribution of data can be described with a few parameters, like the block size and stride.) However, there exist a number of applications (often referred to a "irregular") that are beyond the capabilities of current compilers for HPF. That it, is is either hard or impossible to efficiently map these code onto parallel or distributed systems. The Archimedes project attempts to support such applications, and the Archimedes and Fx compilers share the communication back-end. To address the needs of these applications, however, it is necessary to consider all aspects of the execution environment, including the runtime system. Therefore, one of our current projects investigates the interface between compilers, applications, and the memory and synchronization models provided by the runtime system.

The cmcc compiler is a compact, optimizing C compiler, implemented in C++. This compiler serves as a testbed for research into compiler construction; current topics of interest include code generation, instruction scheduling, register allocation, debugging of optimized code, as well as code optimization to reduce code space and program execution time. In addition, cmcc is a platform to explore code reuse and software construction. A compiler offers ample opportunities for code reuse, and the compiler includes a number of (application) frameworks, including frameworks for global data flow analysis, local instruction scheduling, and register allocation. These frameworks simplify the program structure (and are one of the reasons for cmcc's compactness). They also allow a fair comparison between different approaches (e.g., to register allocation), since different register allocators share the base tools (like building the interference graphs). Finally, a building a framework indicates that we are able to unify a number of so far disparate approaches and thereby expresses our improved understanding of the problem domain.

In summary, my research area includes the programming aspects of current and future systems. This research area can be loosely described by the overlap of compilers, operating systems, and computer architecture.

My principal research interest is in the application of type theory to building and reasoning about programs. The focus of my work is the Fox Project, which I lead with Peter Lee and Frank Pfenning, and the PSciCo Project, which I lead with Guy Blelloch, Peter Lee, and Gary Miller. The Fox Project is concerned with the design, implementation, and application of advanced programming languages. The fundamental thesis of the project is that type theory is critically important for the implementation of robust, maintainable, and efficient software systems. The PSciCo Project is concerned with the application of advanced programming languages to the implementation of sophisticated algorithms for scientific computing.

Type theory provides a unifying conceptual framework for programming language design, specification, and implementation. As a design tool type theory provides a clean framework for organizing programming language constructs. A type consists of a collection of values together with a collection of primitive operations on those values. Familiar notions such as trees or lists may be viewed as values of recursive type; the operations permit traversal of these structures. Procedures may be viewed as values of function type, with operations to create procedures and to apply them to arguments. Abstract data structures such as dictionaries may be seen as values of existential type, with operations to create a data structure and to use a data structure without revealing its implementation details. In fact a programming language may be defined by giving an interpretation of its constructs in type theory. For example, modularity mechanisms might be rendered as uses of existential type, together with a notion of subtyping to admit code reuse and generic operations. A significant advantage of the type-theoretic viewpoint is that it has direct implications for compiler writers. My work on the TIL compiler demonstrates the importance of typed intermediate languages for building compilers that generate efficient machine code. The stages of the TIL compiler are defined as type-directed translations that transform both a program and its type. This allows the compiler to take advantage of type information at compile-, link-, and run-time. The TIL ML compiler generates code that is three times faster and uses half the space of other competing compilers.

Types are also a useful tool for prototyping programming languages and proving properties of programs. My work with Frank Pfenning on the LF logical framework is concerned with the development of a "logic workbench" that allows one to implement formal systems such as type systems for programming languages or logics for reasoning about programs. The LF language is a simple, yet expressive, type theory in which one may describe the abstract syntax and deductive apparatus of a formal logical system. The Elf programming language may be used to build proof checkers and theorem provers for a logic specified in LF. In a recent case study Elf was used to define a small assembly language for network packet filters and to define a logic for stating and proving memory invariants of programs written in this language. The program, together with the LF representation of its proof, form a "self-certified" binary that may be safely installed in an operating system kernel without fear of violating the kernel's memory. Elf has also been used to prototype experimental languages, and to study the properties of logical systems such as Girard's linear logic.

URL: http://www.cs.cmu.edu/~rwh
Fox Project: http://foxnet.cs.cmu.edu
Logical Frameworks: http://www.cs.cmu.edu/afs/cs/user/fp/www/lfs.html

My research interests revolve around the integration of text, image video and audio analysis. In the Informedia Project we have built the News-on-Demand application, which is an instantiation of the Informedia Digital Video Library idea, based completely on automatic methods for processing television and radio news. Through the combination of the strengths of speech recognition, natural language processing, information retrieval and interface design, the system is able to overcome some of the shortfalls inherent in each of the component technologies.

My goal is to utilize large corpora of "found data", that is data that is already available through the Internet or other readily accessible open sources, to improve speech and natural language processing by exploiting advantages across different modalities. It has become clear in recent years that large volumes of text, image, video and audio can be easily stored and made available for research and applications. However, most of these text, image, video and audio sources were not produced with computer processing in mind. My intention is to design and build intelligent, understanding programs that help process data from these sources and make the data useful for other applications. This data can be used to improve speech recognition, image understanding, natural language processing, machine learning as well as information retrieval. The challenge is to find the right data, process it into suitable form for training, learning or re-use and build mechanisms that can successfully utilize this data.

Speech and multimedia technology is about to make a major impact on our daily interaction with computers. What is needed at this point are clear demonstrations of the advantages of integrated speech and multimedia interfaces.

My interests are centered in computer graphics but include related fields such as image processing, computer vision, and scientific computing. I enjoy working with a variety of issues, including mathematical, computational, user-interface, and artistic concerns. A broad summary of my research goals is: the development of algorithms and software tools to facilitate the creation and manipulation of pictures and other multidimensional data. Some applications which motivate much of my work are: computer animation for movies, computer aided design, and scientific visualization for education, science, and engineering. Some of my recent research is in the area of image synthesis, also known as rendering. Realistic image synthesis, the generation of images of mathematically-described three-dimensional scenes that are indistinguishable from reality, is a very challenging goal.

One of the fundamental computational challenges of realistic image synthesis is the simulation of global illumination, the interreflection of light in a 3-D scene. I am currently investigating radiosity methods for doing such simulations, in which a surface is subdivided using a mesh and a large system of equations is solved to compute the brightness of each triangle in the mesh. Our current research involves better methods for meshing that take occlusion into account, wavelet techniques for solving the equations efficiently, and fast methods for generating shadows. Future work will generalize these methods to work well on curved and shiny surfaces.

Another area of my research is surface modeling: their interactive design, their representation, and their efficient display. Prof. Andy Witkin and I developed a particle-based technique that allows very general, interactive design of implicit surfaces. Our repelling particle technique has also been generalized to create a flexible 2-D mesh generator useful for surface meshing in computer graphics and other applications in scientific computing. To speed up the display of complex geometric models, I am currently developing new multiresolution modeling techniques that represent objects at multiple levels of detail. When an object is viewed from up close, a detailed model is drawn; but when viewed from the distance, a coarse approximation is drawn. How do we make multiresolution models quick, accurate, and seamless? Multiresolution techniques have applications in flight simulators, video games, computer aided design, geographic information systems, and cartography. A graduate student and I have recently developed some fast algorithms for simplifying terrain data and more general 3-D objects that generate quite accurate approximations.

This is a summary of my current research, but my interests are not limited to these topics.

My primary research interest is in creating engineering models of human performance to be used in the design of human-computer interaction. Such models seek to optimize several criteria that distinguish them from traditional cognitive models: the ability to make zero-parameter predictions, the ability to be taught to and be used by computer systems designers, coverage of total tasks, and approximation.

Engineering models must be able to make predictions in the absence of a working, or even simulated, system because the predictions are needed early in the design process, where they can be used to shape the specifications of the system. Any parameters used to make the predictions must be set during the development of the modeling technique, not when the technique is being applied to a new situation. This does not mean that parameters have to be fixed constants for every situation, only that they must be determinable a priori. Tables of parameters covering a wide range of tasks can be used to estimate values for a new situation and these are created from research done in the development of the modeling technique. Such graphs or tables build in basic psychology so that computer designers can use the models effectively.

The target users of HCI engineering models are computer system designers, not usually trained psychologists or human factors experts. Thus, the designer cannot be counted on to bring psychological expertise to the task and the basic psychology must be built into the models. Tables of parameter estimates have already been given as an example of building in this expertise. In addition, the procedures must be clearly defined and representative examples must be presented to allow the techniques to be taught. This does not mean that the procedures have to be as structured as recipes in a cook book. However, there must be guidelines and rules about what to do in many representative situations so that a style of analysis can be developed that leads to good predictions.

The activities people perform when interacting with computers are quite varied. These include reading, searching for information on the CRT screen, processing information relevant to task goals, forming plans, typing, pointing, learning, making and recovering from errors, and a myriad of other activities that overlap and interact with each other. Engineering models must do more than focus on each activity in isolation, they must allow prediction of the overlap and interaction between activities. Coverage of total tasks is the most difficult criteria for engineering models to satisfy.

Engineering models of human performance must produce useful predictions at different levels of approximation. Some design situations require gross predictions of performance, e.g., selecting a word processor based on how long it will take to complete some benchmark tasks. Other design situations require much finer grained analyses, e.g. predicting where a combat pilot's visual attention is directed at every moment during a tactical maneuver so the effects of a new visual display can be assessed. Engineering models meet different design needs by providing approximations to the mechanisms that produce behavior. Models of mechanisms and processes allow operations to be grouped, averaged over, or ignored, as appropriate to the design situation.

One engineering model of human performance has been developed over the last decade, GOMS, which forms the basis for my continuing work. GOMS stands for Goals, Operators, Methods, and Selection rules, which are the components of the user's knowledge and task requirements necessary to predict user performance. GOMS has received a decade of academic interest and laboratory research, and has been demonstrated to be a valuable real-world evaluation and design tool for task-specific workstations (e.g., workstations for telephone operators). A current GOMS project models the behavior of architects using complex CAD systems to increase their productivity. I am currently working within the Soar cognitive architecture to extend GOMS and produce more complete engineering models. The current focus of this work is in modeling rapid interaction with the environment. One current project investigates how expert programmers interleave planning and coding and use the information displayed by their programming environment to structure their work. Another project investigates the mechanisms for problem solving and learning in the externally-driven, fast-paced domain of video games. A third models learning in an air-traffic controller task. My secondary research interest is in understanding the usefulness and usability of predictive HCI assessment techniques other than engineering models. I have an ongoing project to apply other techniques (e.g., Heuristic Evaluation, Cognitive Walkthrough, User Action Notation, Claims Analysis) to the design of complex systems (e.g., programming environments, multi-media authoring tools) to determine what types of usability problems these techniques can identify, how much effort it is to learn and use them, to what types of systems and at what stage of development they can best be applied, and how their results compare to empirical methods.

My research interests lie in the areas of network protocols, operating systems, and distributed systems, particularly in the interactions between these areas. Most of my current research is in the area of adaptive protocols for wireless and mobile networking, and I am currently leading the Monarch Project at CMU in this area.

Wireless networks have fundamentally different properties than typical wired networks, including higher error rates, lower bandwidths, nonuniform transmission characteristics, increased usage costs, increased susceptibility to interference and eavesdropping, and higher variability of performance. Similarly, mobile hosts behave differently and have fundamentally different limitations than stationary hosts. For example, mobile hosts generally operate on limited battery power and may move and change their point of connection to the network at any time. These differences in network and host properties produce many new challenges for network protocols.

Our research in the Monarch Project is addressing these challenges through the development of new networking protocols and protocol interfaces to allow a level of wireless and mobile networking support substantially beyond what is possible with traditional protocols. Our goal is to create an integrated set of protocols that allow mobile computers, and the applications running on them and communicating with them, to seamlessly make the most efficient use of the best available network connections at any time. For example, each time a mobile host changes its location, the routing protocols must adapt in order to continue to route packets to the mobile host. In addition, different wireless networking products or services, intended for example for local-area, metropolitan-area, and wide-area use, must make different tradeoffs in factors such as bandwidth, latency, error rate, and usage cost, providing different levels of quality of network connection to the mobile host. With each change in mobile host location, the routing decisions should take these differences into account, and higher-layer protocols and applications on the mobile host and on other hosts communicating with the mobile host should be able to adapt to the characteristics of the mobile host's new network connection.

The Monarch Project covers areas ranging roughly from portions of the ISO Data Link layer (layer 2) through the Presentation layer (layer 6). Our research approach consists of four themes:

• Protocol design and implementation of new protocols for wireless and mobile networking, or improvements to existing protocols to better support this goal. We have developed new protocols for mobile internetwork routing (Mobile IPv4 and Mobile IPv6) and wireless mobile ad hoc networking (DSR), and are also actively working on other protocol areas.
• Performance measurement and simulation of the protocols we develop, to better understand and improve their behavior and to improve their design. We have been very active in the implementation of the protocols we develop, and have also developed a very detailed, realistic wireless and mobile network simulator that we are using in evaluating our work.
• Usage-based evaluation of these protocols, to analyze how the protocols behave in actual operational usage. For example, we have deployed Mobile IP home agents and foreign agents on four major subnets on campus and hope to enlarge our user community to better evaluate the protocol under real usage.
• Active contribution to Internet standards through the IETF, the principal protocol standards development organization for the Internet. Active participation in the IETF (Internet Engineering Task Force) provides a unique opportunity to transfer the results of our research into the Internet community, and we have been very successful at this in our work.

The Monarch Project is named in reference to the migratory behavior of the monarch butterfly. Each autumn, millions of monarch butterflies migrate from central and eastern United States and Canada to overwintering roosts in central Mexico; with the coming of spring, the monarch population again migrates northward. The name Monarch can also be considered as an acronym for Mobile Networking Architectures. Our work is currently funded by NSF, DARPA, the AT&T Foundation, and Caterpillar Inc., and we have also previously received funding from Bellcore, the Carnegie Mellon Information Networking Institute, and AEG Transportation Systems.

My research interests are in the areas of computer vision, visual and multi-media technology, and robotics. Common themes that my students and I emphasize in performing research are the formulation of sound theories which use the physical, geometrical, and semantic properties involved in perceptual and control processes in order to create intelligent machines, and the demonstration of the working systems based on these theories. My current projects include basic research and system development in computer vision (motion, stereo and object recognition), recognition of facial expressions, virtual(ized) reality, content-based video and image retrieval, VLSI-based computational sensors, medical robotics, and an autonomous helicopter.

Computer vision.
Within the Image Understanding (IU) project, my students and I are conducting basic research in interpretation and sensing for computer vision. My major thrust is the "science of computer vision." Traditionally, many computer vision algorithms were derived heuristically either by introspection or biological analogy. In contrast, my approach to vision is to transform the physical, geometrical, optical and statistical processes, which underlie vision, into mathematical and computational models. This approach results in algorithms that are far more powerful and revealing than traditional ad hoc methods based solely on heuristic knowledge. With this approach we have developed a new class of algorithms for color, stereo, motion, and texture.

The two most successful examples of this approach are the factorization method and the multi-baseline stereo method. The factorization method is for robust recovering shape and motion from an image sequence. Based on this theory we have been developing a system for "modeling by video taping"; a user takes a video tape of a scene or an object by either moving a camera or moving the object, and then from the video a three-dimensional model of the scene or the object is created. The multi-baseline stereo method, the second example, is a new stereo theory that uses multi-image fusion for creating a dense depth map of a natural scene. Based on this theory, a video-rate stereo machine has been developed, which can produce a 200x200 depth image at 30 frames/sec, aligned with an intensity image; in other words, a real 3D camera!!

Currently, we are working on a rapidly trainable object recognition method, a system for modeling-by-video-taping, and a multi-camera 3D object copying/reconstruction method.

Visual media technology for human-computer interaction.
A combination of computer vision and computer graphics technology presents an opportunity for a new exciting visual media. We have been developing a new visual medium, named "virtualized reality." In the existing visual medium, the view of the scene is determined at the transcription time, independent of the viewer. In contrast, the virtualized reality delays the selection of the viewing angle till view time, using techniques from computer vision and computer graphics. The visual event is captured using many cameras that cover the action from all sides. The 3D structure of the event, aligned with the pixels of the image, is computed for a few selected directions using the multi-baseline stereo technique. Triangulation and texture mapping enable the placement of a soft-camera to reconstruct the event from any new viewpoint. The viewer, wearing a stereo-viewing system, can freely move about in the world and observe it from a viewpoint chosen dynamically at view time. We have built a 3D Virtualized Studio using a hemispherical dome, 5 meters in diameter, currently with 51 cameras attached at its nodes. There are many applications of virtualized reality. Virtualized reality starts with a real world, rather than creating an artificial model of it. So, training can become safer, more real and more effective. A surgery, recorded in a virtualized reality studio, could be revisited by medical students repeatedly, viewing it from positions of their choice.

Or, an entirely new generation of entertainment media can be developed - "Let's watch NBA in the court": basketball enthusiasts could watch a game from inside the court, from a referee's point of view, or even from the "ball's eye" point of view.

Also, I am interested in and currently working on vision techniques for recognizing facial expression, gaze, and hand-finger gestures. Such techniques will provide natural non-intrusive means for human-computer interface by replacing current clumsy mechanical devices, such as datagloves.

Informedia Project.
With the growth and popularity of multimedia computing technologies, video is gaining importance and broadening its uses in libraries. Digital video libraries open up great potentials for education, training and entertainment; but to achieve this potential, the information embedded within the digital video library must be easy to locate, manage and use. Searches within a large data set or lengthy video would take a user through vast amounts of material irrelevant to the search topic. The typical database, which searches by keywords (e.g. title) - where images are only referenced and not directly searched for - is not appropriate or useful for the digital video library, since it does not provide the user a way to know the contents of the image, short of viewing it. New techniques are needed to organize these vast video collections so that users can effectively retrieve and browse their holdings based on their content. The Informedia Digital Video Library, funded by NSF, ARPA, and NASA, is developing intelligent, automatic mechanisms to populate the video library and allow for a full-content knowledge-based search, retrieval and presentation of video. The distinguishing feature of Informedia's approach is the integrated application of speech, language and image understanding technologies.

Computational Sensor.
While significant advancements have been made over the last 30 years of computer vision research, the consistent paradigm has been that a "camera" sees the world and a computer "algorithm" recognizes the object. I have been undertaking a project with Dr. Vladimir Brajovic that breaks away from this traditional paradigm by integrating sensing and processing into a single VLSI chip a computational sensor. The first successful example was an ultra fast range sensor which can produce approximately 1000 frames of range images per second an improvement of two orders of magnitude over the state of the art. A few new sensors are being developed including a sorting sensor chip, a 2D salient feature detector (2D winner-take-all circuits), and others.

Medical Robotics and Computer Assisted Surgery.
The emerging field of Medical Robotics and Computer Assisted Surgery strives to develop smart tools to perform medical procedures better than either a physician or machine could alone. Robotic and computer-based systems are now being applied in specialties that range from neurosurgery and laparoscopy to opthalmology and family practice. Robots are able to perform precise and repeatable tasks that would be impossible for any human. The physician provides these systems with the decision making skills and adaptable dexterity that are well beyond current technology. The potential combination of robots and physicians has created a new worldwide interest in the area of medical robotics. We have developed a new computer assisted surgical systems for total hip replacement. The work is based on biomechanics-based surgical simulations and less invasive and more accurate vision-based techniques for determining the position of the patient anatomy during a robot surgery. The developed system, HipNav, has been already test-used in clinical setting.

Vision-based Autonomous Helicopter.
An unmanned helicopter can take maximum advantage of the high maneuverability of helicopters in dangerous support tasks, such as search and rescue, and fire fighting, since it does not place a human pilot in danger. The CMU Vision-Guided Helicopter Project (with Dr. Omead Amidi) has been developing the basic technologies for an unmanned autonomous helicopter including robust control methods, vision algorithms for real-time object detection and tracking, integration of GPS, motion sensors, vision output for robust positioning, and high-speed real-time hardware. After having tested various control algorithms and real-time vision algorithms using an electric helicopter on an indoor teststand, we have developed a computer controlled helicopter (4 m long), which carries two CCD cameras, GPS, gyros and accelerometers together with a multiprocessor computing system. Autonomous outdoor free flight has been demonstrated with such capabilities as following pre-scribed trajectory, detecting an object, and tracking or picking it from the air.

My fundamental research interest is in the nature of computation as it occurs in the hardware of the human mind. Unlike computers, humans make great use of visual representations (such as diagrams, tables, and symbols) and their everyday knowledge in solving mathematical problems. The important role of everyday knowledge in human computation is illustrated by our experimental result that, despite popular belief, students are better at solving certain algebra word problems than the corresponding equations. Empirical studies are the first step in understanding how people use visual representations and world-knowledge in problem solving and learning. But this understanding is made firm in the creation of cognitive models that simulate such processes. An example of one such model, called DC, uses "diagram configurations" to model how the perceptual intuitions of geometry experts allow them to make leaps of inference in theorem proving.

The practical test of my basic cognitive research is the construction of computer-based "cognitive tutors" designed to improve the learning of mathematics and science. Cognitive tutors for algebra and geometry are being extensively tested in high schools and colleges and have been shown to lead to a standard deviation, or grade level, improvement in student performance. A major project is under way in the Pittsburgh public schools to attempt to show that the use of cognitive tutors for 3 years of high school math can lead to learning gains equivalent to a 100 point improvement in math SAT scores. Underlying systems research is addressed at the development of an architecture for "plug-in tutoring agents" that can be embedded within learning and work environments to tutor the use of commercial software (like spreadsheets) in computer-supported problem solving

Dr. Kraut conducts empirical research on how individuals, groups and organizations use new computing and communications systems. Topics include office automation and employment quality, communication and home-based employment, the communication needs of collaborating scientists, the design of information technology for small-group intellectual work, and the impact of national data networks. Dr. Kraut is currently interested in the design and evaluation of computing systems that conserve and distribute organizational memory.

Language Technologies.
One of the most challenging, fascinating, and applicable areas of research in human language technologies is the design of computational models of language as a statistical source. Suppose that we were to play a game where I read to you from the The New York Times and periodically ask you to guess the identity of the next word. The entropy of the Times is the average number of yes-or-no questions that you need to ask---if you're as clever as you can be---to determine the identity of the word. The goal of language modeling is to develop computer programs that play this game well. The notion of entropy provides a mathematical foundation on which to build solutions to this problem. We have recently used language models as the basis for a new approach to unsupervised clustering of documents and words; such clustering algorithms are important for a wide variety of tasks in information retrieval, natural language and speech processing.

Statistical Learning Algorithms.
Many of the tasks that we work on in language technologies use machine learning algorithms to extract patterns from historical data to predict future behavior. An example is our work on text segmentation in which we build an exponential model to extract relevant features of the surrounding text to determine where to place story boundaries. There are fascinating connections between these techniques and "boosting" algorithms in machine learning, as well as more classical regression techniques in statistics. We are working to develop the links between these different areas, and to formulate them in terms of a general computational framework for statistical inference.

Coding and Information Theory.
Algorithms on graphical structures play a central role in both communications technology and formal verification. We have recently established a close correspondence between trellises, which are widely used in the construction and decoding of error-correcting codes, and binary decision diagrams, which have found widespread use in computer-aided design and formal verification of digital circuits. Based on this bridge, we are working to transfer ideas between these previously disparate fields. The fundamental problem that confronts both uses of graphical methods is the same: devise techniques to combat the exponential blowup in the size of the graph. In addition to coding and verification, we are also investigating applications of the underlying ideas to such areas as database search.

My research is in the design and implementation of advanced programming languages. I am especially interested in approaches based on principles from formal semantics and type theory, with a particular emphasis on applications in operating systems and networks. Much of my work is centered around the Standard ML programming language (SML) and its theoretical underpinnings. SML provides many advanced features, including first-class functions and continuations, polymorphic types with automatic type inference, garbage collection, and a powerful system for specifying parameterized modules. Jointly with Robert Harper, I work on the Fox Project, which is using SML to implement high-speed network communication protocols. Not surprisingly, we get great benefits from the expressive power, type safety, and support for modularity and composability provided by SML. As a result, our networking system is extremely reliable and easy to reconfigure for special-purpose applications. (You can try out our web server written in SML. This is also a good way to get more information about the Fox Project.)

Using SML directly for systems programming is just the tip of an iceberg, however. What is actually more significant than the language itself is the theoretical foundation that has been developed for the language. This theory has the potential for applications beyond the realm of the SML language itself. The main areas for my focus are the following:

Proof-Carrying Code.
One problem that is becoming more important in distributed and web computing is how one agent (the code consumer) can be assured of safety when it executes code supplied by another agent (the code producer). Instead of using expensive run-time mechanisms such as separate address spaces or dynamic fault checks, Proof-Carrying Code (PCC) requires that the code producer to supply a proof that the code is safe. The proofs are written in a special language (without any use of cryptography) so that the code consumer can know with total confidence that the code is safe. To date, the concept and some limited demonstrations of PCC have been developed, but much more work needs to be done in order to make it fully practical.

Program Analysis and Transformation.
The ML language has a well-defined formal semantics, which forms an excellent basis for developing static analyses and optimizations. However, some of the advanced features of the language, such as higher-order functions, make it hard to get precise information from a static analysis. My students and I have been working in the general mathematical framework of Abstract Interpretation to overcome these problems.

Run-Time Code Generation.
There are many situations, especially in systems such as network protocols, where information that would be useful for compiler optimization becomes available only at run time, but once available, it remains relatively static. In such cases, it is often profitable to delay some optimization and code generation until run time. I have been working on using techniques from partial evaluation to achieve very fast and effective run-time optimization and generation of ML programs, so as to exploit these kinds of situations. For example, using a prototype system, we can demonstrate an interpreter for Berkeley Packet Filters written in ML. Our system achieves a 40% reduction in per-packet latency over the Berkeley C implementation. The unifying theme of all of these research problems is the exploitation of the underlying semantics of the programming language. It is my strong belief that this will be one of the keys to new approaches to software development.

My research involves the application of computational, modeling and electrophysiological techniques to study the neural basis of visual perception and recognition. The current effort of my laboratory is focused on the following scientific issues in the areas of computational neuroscience and computational vision.

The first issue concerns with feedback and hierarchical computation in the visual system. The classical paradigm for vision, as delineated by Marr, is that vision is accomplished by a series of feedforward computations in the visual hierarchy. The experimental findings from my laboratory show that global contextual information can modify the computation in early visual areas, presumably mediated by the massive recurrent feedback from the higher level cortices to the earlier ones. What is the functional role of this feedback? What are the advantages of the concurrent and interactive computation across the visual hierarchy? To address these questions, we are constructing and testing computational models and realistic neural circuits in conjunction with recording from neurons across the visual hierarchy while the monkeys are observing stimulus patterns of different complexity.

The second issue concerns with the dynamic and active aspects of vision. Much of the vision research has focused on the analysis of patterns in static situations by the visual system or by computer. Vision in reality is an active and dynamic process. Our eyes move constantly, purposefully scanning the environment to construct a coherent internal representation of the scene based on the retinal data, which is precise only in the fovea. How are these bits and pieces of retinal information assembled and integrated over time to form a seemingly coherent picture of the world? How and where are these scene elements represented in the brain? To address these questions, we are conducting human psychophysical experiments to examine information transfer across saccadic eye movements, formulating and testing computational models for scene integration, recording from neurons when monkeys are actively scanning and searching in the visual environment.

The third issue concerns with neural plasticity and learning. The brain is an adaptive system. Even after development, the neural circuits remain plastic and exhibit changes with learning. Currently, we are implanting electrode arrays of 100 electrodes into the monkeys' neocortex to record from the same neurons in the visual system over long periods of time (months) during which the monkeys will be trained to perform new perceptual grouping and perceptual discrimination tasks. The experiments are inspired by unsupervised and reinforcement learning models, but we hope to infer from the neurophysiological data the neural algorithms underlying the development, formation and maintenance of neural circuits in the visual hierarchy.

The fourth issue concerns with the structure of neural code For the last thirty years, the average firing rate of the neurons has been considered to be the most reliable measure of neural information. We are analyzing single and multi-electrode data to examine the possible existence of precise temporal spike pattern hidden in the neural spike trains that may encode higher order structures using various pattern analysis, machine learning and statistical techniques.

By elucidating the neural code, representations and algorithms underlying biological computation and learning, we hope not only to gain a better understanding of the mind and the brain, but also to discover new and more powerful ways to build learning systems and robots.

My research focuses on computational approaches to understanding cognition, especially the human language capability and its relationship to human and machine learning. My approach includes both the creation of fine-grained computational models of language processing and the creation of environments for augmenting and facilitating human-computer language interactions. Past research includes the creation of an adaptive natural language interface (CHAMP) that learned the idiosyncratic grammars of different individuals. Together with students, I subsequently developed two systems within the Soar architecture. EFH-Soar was a project that studied the efficacy of education in microworld environments through modeling and empirical testing. NL-Soar, my main focus during the past seven years, is a comprehensive cognitive model of adult language comprehension and production, integrating language, learning, problem-solving and action in a unified framework. Most recently I have refocused my research toward developing a computer-based environment for remediating language in language-disordered children -- work that builds directly on my previous experience with adaptive interfaces, human language modeling, and education in microworlds.

Unlike other software intervention, Simone Says is designed to be a speech-based, interactive environment intended initially for young, non-mute children with autistic spectrum disorders. It creates opportunities for meaningful, verbal language practice across a wide range of linguistic tasks in a simple social world. Tasks cover vocabulary, basic syntax, semantics and pragmatics, joint attention, conversational turn taking, and simple conversational repair. The system's design combines sound clinical practice with the engaging features found in off-the-shelf early learning software, including child-centered control, animation and sound, and readily-available help in the form of animated character guides. It is the child who decides which object(s) to talk about from those visually available and what to make the object(s) do. However, in all instances only referentially meaningful utterances produce an animation, with modeling available if the child cannot produce one. When a language concept is first introduced, the child is unlikely to give a meaningful response to the visual image. In this circumstance, using Simone Says is like a linguistic game of Simon Says: Simone models, the child repeats. As the child's language grows, however, using the system becomes more like verbally clicking on visual hot spots: meaningful speech produces meaningful action on demand. From the child's perspective, increasing proficiency is rewarded by increasing control. Creating Simone Says requires a number of advanced technologies. A primary requirement is a speaker-independent, continuous speech recognition system (such as SPHINX-II) with an acoustic model that can be adapted to young children's voices. Simone Says also requires a method for dynamically tracking the child's language development (such as the one in CHAMP) in order to construct the next target example and provide a constrained language model to the recognizer. Finally, the system must have a method for translating the linguistic description of the next example into a visual image and animation that can dynamically accommodate variation along dimensions such as color, size, number of objects, participation of animated characters, and substitution of objects from the same semantic class. The off-the-shelf animation authoring environment Director seems to be adequate to the task. Each of the components is understood well enough to make an initial implementation of Simone Says feasible. The main contribution clearly lies in bringing all these independently-developed technologies together into a coherent, engaging, and pedagogically effective real-time environment.

My main interests are in the areas of high performance distributed computer systems and networking. I work with faculty members associated with DARWIN, whose goal is to define, implement and evaluate application-aware resource management mechanisms for networks and the Remulac project whose goal is to support the development of applications that need advanced features of modern networks such as resource reservations and quality of service guarantees Both of these project include substantial applications that involve groups both inside and outside of CMU. My role is primarily project management and partnership relationships.

My research area is networks for parallel and distributed computer systems. For the past few years my research has focused on how to build the communications system that underlies a parallel computer. My goal has been to develop mechanisms for moving data between processors (or between processors and memory) that are both practical and provably effective. To this end, I have designed, analyzed, and implemented algorithms for routing, sorting, and tolerating faults in parallel computers.

As an example of this type of work, Berthold Voecking and I have recently shown that an N-node AKS network can be embedded in a 3N/2-node degree-8 multibutterfly network with load 1, congestion 1, and dilation 2. The result has several implications, including the first deterministic algorithms for sorting n keys on an n-input multibutterfly in O(log n) time, and a three-dimensional VLSI layout for the n-input AKS network with volume O(n^(3/2)). These algorithms provide further evidence of the robustness of multibutterfly networks. We have also discovered a separate, and more practical, deterministic algorithm for routing h relations on an n-input multibutterfly in O(h+log n) time. Previously, only algorithms for solving h one-to-one routing problems were known.

Micah Adler and I have been studying asymmetric networks. An asymmetric network is one in which the link bandwidth or the link reliability between two points u and v differs according to the direction u -> v or v -> u. My interest in this subject was sparked by a hobby of mine. Over the past few years I have established a high-speed internet connection between campus and my home. The link is asymmetric because it uses 2 megabit/second wireless Ethernet in one direction and a 33.6 kilobit/sec telephone line in the other. (The reason for this asymmetry is that there is too much radio-frequency noise on campus for a signal to get through from off campus.) Despite the asymmetry, the link has proved capable of supporting a remote X terminal and a web browser, thus allowing me to work from home in a graphical environment comparable to that of the workstation in my office.

Micah and I have devised protocols for transmitting information across an asymmetric communication link in the ``wrong'' (or slow) direction. We assume that a client has an n-bit data item drawn from a distribution D to transmit to a server, and that the distribution is known to the server, but not to the client. This model is motivated by the scenario in which a server is collecting a single data sample from each of many clients. We have shown that using the asymmetric link in the fast direction, the server can guide the client through a transmission in which the client does nearly as well without knowing the distribution D as it could knowing D. In particular, we have devised a protocol in which the expected number of bits sent by the server is at most 3n, while the expected number of bits sent by the client is at most 1.71H(D), where H(D) is the entropy of the distribution D. Even knowing D, the client cannot expected to send fewer than H(D) bits. We have developed variations on this protocol in which the number of handshakes between the client and server is reduced, and also proved matching lower bounds and impossibility results concerning the total number of bits sent, the amount of computation performed by the server, and the number of handshakes.

My research now continues on a new front: parallel algorithms for scientific computing.

Claudson Bornstein, Gary Miller, R. Ravi, and I have been studying the problem of solving linear systems using direct methods such as Gaussian elimination. We have focused on nested dissection. Viewing a system of equations as a graph, nested dissection can be summarized as follows. First find a set of ``separator'' vertices whose removal partitions the graph into two or more connected components. These vertices will be eliminated last. Order the individual components one after the other. (The separator prevents ``fill'' between the different components.) Within each component, order the vertices recursively.

We have analyzed the performance of a parallel variant of nested dissection that can be applied directly to interval graphs and chordal graphs. For general graphs, the algorithm can be used to parallelize the ordering produced by some other heuristic such as minimum degree. In this case, the algorithm is applied to the chordal completion that the heuristic generates from the input graph. The input to the algorithm is a chordal graph G with n nodes and m edges. The algorithm produces an ordering with height at most O(log^2 n) times optimal, fill at most O(m), and work at most O(W(G)), where W(G) is the minimum possible work over all elimination orderings for G. Experimental results show that when applied after some other heuristic, the increase in work and fill is usually small. In some instances the algorithm obtains an ordering that is actually better, in terms of work and fill, than the original one.

Claudson, Gary, and I have also analyzed a new sequential variant of nested dissection based on the following idea: once all but one of the components has been eliminated, the separator need not be eliminated last. We have developed a heuristic for determining when to eliminate the separator last, and when to merge it with the last component. In practice, our heuristic has been shown to outperform all of the publically available codes for nested dissection in terms of work and fill. The heuristic also has a theoretical motivation: unlike standard implementations of nested dissection, when applied to chordal graphs it produces a zero-fill elimination order.

I want to build intelligent robots---robots that would perceive and manipulate physical objects as cleverly and effectively as humans. At present, robots are unable to reason about physical processes, so robot motions have to be pre-programmed in complete detail. As a result, robots are extremely limited in the tasks they can perform. They are clumsy, virtually blind, and cannot react to unexpected events. By giving it the ability to reason about physical processes, I hope to build a robot able to predict the effect of its actions, or to plan a sequence of actions to achieve its goals.

The chief complication is uncertainty. Objects are never exactly where they should be, nor are they exactly the expected shape. Also, the robot's motions are imprecise, the sensors are noisy, and all of the relevant physical parameters, such as the coefficient of friction, are hard to predict. A robot can deal with uncertainty in two ways: it can adjust its model and its actions based on sensory feedback, and it can choose actions that are insensitive to variations in the world. Underlying both of these options, a robot must include uncertainty in its model of objects and physical processes.

My research efforts are organized around three inter-related problems: Autonomous Manipulation in Simple Task Domains. A good way to explore the issues of automatic planning is to design simple worlds, in which the problems of greatest interest can be isolated from tangential complications. We have built planners that manipulate simple shapes in two-dimensional worlds, and have demonstrated the systems using an industrial robot in the Manipulation Laboratory.

Mechanics of Manipulation.
To build robots that understand the physical processes of manipulation, we first must understand these processes ourselves. Manipulation takes place in a world often dominated by friction and collisions. Combined with our interest in uncertainty, these novel aspects have generated interesting new problems in classical mechanics.

Learning Robot.
An intelligent robot needs a model of the world to predict the effect of its actions, and to choose useful actions. But where does the model come from, and how does it evolve? In collaboration with Tom Mitchell, we are working on a robot that will watch the world and use its observations to revise its model. Such incremental adjustments to the model may partly explain how performance improves with experience.

RESEARCH GOALS.
Our goal is to make computer systems robust and safe. We are trying to understand why computers fail, and what can be done about it. This includes circumstances in which people fail when operating computers, as well as circumstances of autonomous operation. We are solving dependability problems by engaging in the design, implementation and evaluation of a wide variety of highly dependable systems (including their user interfaces) for mission-critical environments (e.g., hospital patient monitors, air traffic control systems, semiconductor wafer-fabrication process-control environments, and national infrastructure systems such as banking, communication and electric energy networks). By making systems more dependable, the consequences of downtime, such as monetary losses exceeding tens of thousands of dollars an hour, or loss of life, can be avoided.

OVERVIEW.
According to popular wisdom, about 95% of all errors are created by the systems under which we work. Computer systems are no exception; many people have personal experience with errors in hardware and software. Human error in conjunction with computer systems is now responsible for as much as 80% of system unavailability; when systems fail, 65% of the recovery effort is spent in diagnosis. Consequently, two important thrusts for our work lie in dependable user interfaces and automated real-time diagnosis, both of whose goals are to mitigate error and to reduce downtime along with its associated costs. Our work is highly quantitative and very much measurement- and data-driven. We conduct careful empirical and theoretical performance evaluations of all our systems; some of our research also involves the design and implementation of evaluation methods themselves.

Computer System Failure.
Computers have always been subject to hardware failures, most of which can be mitigated through the use of fault tolerance. Now that the mean time between hardware failures exceeds 40,000 hours, software failures appear to dominate undependability statistics. As progress is made in solving the problem of software reliability, the dominant cause of outages is likely to shift to those that are operator-induced, suggesting that the failures reside in the user interface. Sometimes these modes are mixed, such as when a software fault is the result of a programmer's failure to recognize and handle exceptions correctly. More recently, the growth in scale and complexity of computer systems has exacerbated the problem of making systems of systems robust to failure. One example is the Internet, which is subject not only to traditional failures, but also to malicious attacks such as denial of service, information theft, and intrusion and corruption by unauthorized users. Because corporations and nations have come to depend so heavily on computer-based information and infrastructure, some pundits have claimed that the next great war will be fought in information space, where foreign operatives use the Internet or other means in attempts to steal corporate secrets, disable regional power grids, cripple a nation's telephone system, or destroy a nation's military command and control system.

CURRENT PROJECTS:
Detection, Diagnosis And Compensation For Failures.
Detecting and interpreting unanticipated failures (failures that no one ever thought of during system design), including human interaction failures, is one focus for our research activities. We are building systems that cope with failures by learning about the characteristics of their own environments. One example lies in semiconductor wafer fabrication, one of the most complex manufacturing process known to mankind, in which we have conducted real-time fault-detection and diagnosis experiments in an operational semiconductor plant, achieving 100% correct diagnosis of faults injected during the course of producing over 46,000 customer wafers.

Intrusion Detection - Combating Information Terrorism/Warfare.
Our work in intrusion detection is closely related to our work in fault detection and diagnosis, and includes the construction of synthetic environments for validating the intrusion detection systems we field. We regard intrusions to be examples of unanticipated anomalous conditions, and we treat them as we do anomalies in hardware and software systems.

Dependable User Interfaces.
Undependable user interfaces are the Achilles' heels of highly dependable systems. Even if a system's hardware and software underpinnings are completely reliable, user-interface errors can cripple or destroy a mission. Our objectives are to mitigate these errors (and corresponding downtime) through careful design of predictably dependable systems, and to provide measurable confidence of dependability in user interfaces. This research is investigating what makes user interfaces dependable, what are the sources of human error, and what are the limitations of the human operator? It seeks an understanding of how such knowledge can be coupled with interfaces that can be depended on to work, as needed, the first time. User and system modeling are major constituents of ongoing efforts. The research incorporates work on human error, robust evaluation, methodologies for requirements analyses, task and user modeling, design and testing of predictably dependable interfaces, fault tolerance and reliability, quantitative metrics and instrumentation, and empirical and experimental methods.

Evaluation Workstation (Metristation).
The seriousness of user-induced failures demands that practitioners and scientists develop tools and methods for evaluating the efficacy and dependability of user interfaces before they are deployed. In this context, dependability is the probability that the system will work the first time it is used. User-interface evaluation is often tedious, time-consuming, error prone and not very robust. The very tediousness of effective evaluation frequently prevents researchers from engaging in it. The Evaluation Workstation project endeavors to reduce the tedium and inaccuracy of these analyses, and at the same time speed them up. It includes timestamped keystroke, mouse-click and event capture; digital audio for verbal protocols; digital video for video protocols; and eye tracking.

Data Mining-Structure Discovery In Large, Uncontrolled Data Sets.
Detection and diagnosis of faults usually necessitate recognizing known patterns or structures embedded in monitored data. If the system environment is novel, as it is in most new products or for new medical patients, then few if any known patterns exist. Such patterns must first be discovered before they can be employed in detection processes. This project seeks to understand how patterns can be discovered in large data sets monitored from such applications as manufacturing process control, networked communications, medical operating rooms, international banking transactions, intrusion-detection systems and others.

Synthetic Data Environment.
How do we gain confidence in a system's ability to detect failures, anomalies or performance perturbations? This project's goal is to build a synthetic environment that can be used for validating fault/intrusion detection systems. We expect it to be made available on the World Wide Web for anyone to use. It will have the capability to replicate environmental conditions faithfully and repeatably, and will be easy to use for both experts and novices. Safety Cases For Dependability. We are exploring the use of formal legal argumentation to support claims of system dependability. One example is justifying safety claims for fly-by-wire or drive-by-wire systems. Another example is justifying claims that a fault-diagnosis system will detect all unanticipated faults.

I am interested in Parallel-Distributed-Processing (PDP) models of perception, memory, language and thought. PDP models assume that cognitive processes in humans emerge from the interactions of large numbers of simple processing units. Each unit is very simple, in that it computes a monotonic function of a weighted sum of its inputs from other units, and adjusts its output accordingly. However, large networks of such units can exhibit intelligent behaviour, and lead us to new conceptions of the basis of intelligent processing. For example, representations in PDP networks are patterns of activation. These representations differ from representations in conventional computers in that they cause patterns to evolve and change (via the connections among units), without the requirement of the intervention of a CPU to interpret their content and take appropriate action. Knowledge in these networks is stored in the strengths of the connections among the units. This means that learning occurs not through the formulation and testing of explicit rules, but through the adjustment of the strengths of the connections among the units.

In recent years, my research has come to focus on issues related to learning, memory, and development, in a cognitive neuroscience context. In McClelland, McNaughton and O'Reilly (Psychological Review, 1995, 102, 419-457), we have developed a complementary learning systems perspective. On this view, the need to learn in ways that are sensitive to the general structure of events and experiences is computationally incompatible with the need to learn the specific contents of particular events and experiences. Complementary memory systems that use very different types of representations and very different parameters of learning are required to address these incompatible goals. Initial work focussed on the second, 'episodic' memory system, which is thought to be associated with the hippocampus and related structures in the medial temporal lobes (O'Reilly and McClelland, Hippocampus, 1994, 4, 661-682; McClelland and Goddard, Hippocampus, 1997, 6, 654-655). Currently, work focusses primarily on the structure-sensitive system, thought to be the basis for our acquisition and use of structured knowledge in a wide range of domains including the semantics of everyday objects, the structure of language, our intuitive understanding of the physical world, etc. Munakata, McClelland, Johnson, and Siegler (to appear in Psychological Review, 1997, 104, October issue) develop a computational model of the acquisition of Object Permanence knowledge. Other work in preparation addresses the acquisition and dissolution of semantic knowledge of everyday objects. Some of the most important current work relates to the hypothesis that learning in the neocortical system is Hebbian in character. This hypothesis is used to account for the apparent stability of language representations when persons from one language community attempt to learn a new language in adulthood, and to account for recent evidence that there may be far more plasticity in the language system than this apparent stability suggests, as indicated by remediation studies that appear to work because they rely on principles of Hebbian learning.

My background is in photogrammetry, the use of images to make precise measurements; my work here in the Digital Mapping Laboratory with Dave McKeown is concerned with the integration of rigorous photogrammetric techniques into image understanding algorithms.

I focus on realistic cartographic scenarios, using aerial mapping imagery and performing resections to determine the image location and orientation. Using this information about the image, always available in a cartographic environment, allows us to make much stronger statements about the geometric and metric properties of the scene and to reference external sources of information such as digital elevation models and feature data. I also study the geometric properties of images for ways to utilize the geometry in scene understanding. For instance, we have used the vanishing point geometry, calculated from the image orientation, to identify possible vertical and horizontal lines in the scene. These attributions are used in two monocular building extraction systems developed by Jeff Shufelt, VHBUILD and PIVOT, to help form and prune building hypotheses. The calculated measurements of scene features also aid in hypothesis evaluation and testing.

Along with imaging geometry, I am exploring the use of object-space geometric constraints to aid in the recognition, extraction, and precise measurement of buildings or other objects whose geometry is partially or completely known or can be inferred. I have extended statistical approaches used for data editing to the examination of these geometric constraints, to detect situations where the assumed geometry is incorrect--the constraint equations are not valid. An important part of standard photogrammetry is error analysis. I am extending traditional point error measures to extracted image features and then using these error estimates in feature fusion and evaluation for scene interpretation.

The use of rigorous photogrammetry is particularly important in stereo matching, especially for stereo pairs with oblique viewing geometry. Steven Cochran has shown that precise reprojection into epipolar alignment produces measurably better results than standard image warping approaches. In the future we will be looking at estimating the precision of the stereo match, based on parameters such as imaging geometry and image frequency content.

Another area of research in the MAPS lab is the classification of high-resolution multispectral and hyperspectral imagery and its fusion with panchromatic aerial imagery. I am working on the precise registration of the imagery, obtained from line scanners and linear pushbroom sensors, and the exploitation of its spectral and geometric properties for cartographic feature extraction.

I am also interested in optimization techniques, especially in the parallels between standard and robust least-squares adjustment as practiced in the photogrammetric community and energy-minization optimization techniques currently popular in the computer vision field. The underlying mathematics are basically similar; by "switching metaphors" from statistical to physical properties and back we can combine statistical concepts such as the standard deviation of a measurement with physical concepts such as the amount of force an operator must exert to move an object. This has potential for semi-automated image exploitation, yielding a good interactive metaphor while maintaining rigorous interpretations of inputs and results.

My research interests are in computer vision, remote sensing, cartography, and large-scale spatial databases. Within the Digital Mapping Laboratory we have a number of research projects each with components in image understanding and remote sensing, photogrammetry and cartography, and computer graphics.

Most recently our focus has been on a set of issues involving the rapid construction of virtual world databases for visual simulation. These databases require the integration of information from digital cartographic products, aerial and satellite imagery, and ground-based photography. They also require intelligent database compilation techniques to support maximal fidelity of the geo-spatial virtual world while using bounded, and often highly limited, visualization resources. In computer vision our research includes the automated analysis of traditional mapping photography as well as emerging multispectral and hyperspectral sensors. There is a common theme involving the fusion of information derived from multiple methods and reasoning about multiple plausible object space interpretations. There is a strong bias toward tying scene analysis 'to the ground' as a way to demonstrate and evaluate research progress.

My main interest is in algorithm design and parallel computation. For the last several years I have worked parallel algorithm design for problem arising in Scientific computation. This includes problems such as fast linear system solvers and mesh generators. Over the last several year our group has developed a large suit of fast and efficient algorithms for these types of problems.

Starting this year, in collaboration with faculty members Guy Blelloch, Bob Harper and Peter Lee, we have begun an ambitious project funded by the NSF to develop a Scientific computing package in a parallel extension of the language ML. I am very excited about this project for it will draw on the talents of the worlds best compiler, language, and parallel algorithm designers. We will be able to test and refine parallel scientific algorithms in a modern environment, as well as, tune the language and compiler to fit the applications.

I am interested in many areas of computer science, but especially in how to construct computers that learn from experience. At the heart of the problem of machine learning is the question of how to automatically formulate general hypotheses given a collection of very specific training examples. My research has addressed a number of approaches to this question, including statistical approaches that find regularities over large numbers of training examples, and analytical approaches that generalize from very few examples and rely instead on prior knowledge and reasoning.

Much of my current research focuses on developing software agents that learn about the world wide web. For example, my students and I recently developed a web browser that accompanies users from page to page, and learns to suggest hyperlinks that will be of interest to the current user. My main current project seeks to automatically construct a huge knowledge base whose content mirrors the world wide web. To see the motivation, consider the fact that your workstation can now retrieve any of 300,000,000 web pages, but it understands none of these pages -- they were written to be human readable, not machine readable. The goal of this research project is to use machine learning to train a web agent to automatically extract probabilistic, symbolic knowledge by reading the web hypertext. If successful, this would lead to a huge world-wide knowledge base that would make the web understandable to computers as well as people. This could be used for much more intelligent information retrieval, or as a large knowledge base for problem solving. Research issues here include inventing learning algorithms that will operate over hypertext, using previously extracted knowledge to guide subsequent learning, and combining natural language processing methods with machine learning.

In addition to my own research, I also direct CMU's new Center for Automated Learning and Discovery (CALD), an interdisciplinary center with faculty from computer science, statistics, GSIA, philosophy, engineering, and other departments. The mission of CALD is to invent new approaches to using historical data to improve future decisions. For example, within CALD we are studying problems such as using historical medical records to predict mortality rates in future pneumonia patients, using historical data on violent criminals to predict which will be repeat offenders, and using historical data describing credit card customers to identify future fraudulent behavior. I would be happy to discuss CALD and its research projects with interested students, and to help identify other CALD faculty with relevant interests.

My research interests center on Machine Learning and Reinforcement Learning with a particular emphasis on learning algorithms for self-improving factories, robot motion planning, adaptive control, industrial engineering. My primary goal is to help make AI become sufficiently practical, powerful and robust that is routinely used in controls and manufacturing industries. My ongoing projects:

General Memory Based learning.
A key component of any autonomous system is that it is able to constantly monitor itself and notice unexpected behavior such as unmodeled dynamics, changing dynamics or, in some cases, equipment malfunction. To do this, we make the system learn from experience. Our research has produced a highly automatic learning mechanisms. The controller explicitly remembers all its sensory experiences (typically such data is in the form of large vectors of real-valued numbers) in a large database of cases. Novel search algorithms are used to persistently monitor the database to spot unexpected trends, relations between variables, and opportunities for controller enhancements.

Reinforcement Learning.
This is an exciting new discipline in which systems learn to control themselves optimally based on arbitrary reward and punishment signals. The central issues concern processing such signals to develop optimal controllers. Our recent research involves scheduling search control during on-line planning to minimize wasted computations. Ongoing research extends this to the PartiGame algorithm, in which exploration and planning are scheduled in a multi-resolution manner. A recursive partitioning of state-space adapts itself in real time to yield fine detail in the critical regions, while remaining at a coarse granularity elsewhere. We are also investigating combining state-space triangulations and tree-search methods to combat to curse of dimensionality.

Auton: AI-based Evolutionary Operation.
Response Surface Methods (RSMs) are a heavily used, statistical technique used in the optimization of expensive industrial processes. Such processes are typically characterized by: a set of controllable parameters, a noisy measurement of the result of running a process with the given inputs. We desire to find the set of parameters which optimizes some measure of the result. Experiments are expensive, but there is plenty of computation time available between each experiment. Current RSM practice is, for sensible reasons, a far from automatic process. It is very possible that techniques from Machine Learning and AI may be of use in RSM applications. We have embarked on the production of a minimal-human-supervision controller for such systems, which watches and adjusts process over extended periods of use: persistently designing safe experiments and whenever appropriate improving the process.

Dealing with Massive Datasets.
In new research, we are examining the computational issues involved with massive datasets, including the Edinburgh-Durham Sky Catalogue of over a million galaxies. We are examining generalizations of kd-trees and R-trees for caching information sufficient to permit answers to extremely wide classes of statistical questions in near-constant time.

I am interested in Computer-Mediated Human Communication. At the low end this involves the engineering of distributed communication systems and the design of document interchange strategies. At high, or human, end it involves activities like calendar management, goal reconciliation, and group processes. The specific projects I'm currently involved with The Prep Editor, a collaborative writing tool, and Team-Centered Design, a new study of collaborative tools and methods for tasks such as crisis management.

My research interests are in speech recognition, Hidden Markov modelling, and speech applications that involve large vocabulary recognition. Currently, large (unlimited) vocabulary speech recognition requires the dedicated use of the most advanced CPUs and large amounts of main memory. I am interested in finding the "right" modelling approach and corresponding search algorithms that will reduce these requirements so that high-accuracy, unlimited vocabulary speech recognition can be brought to the ordinary PC. Secondly, speaker-independent speech models allow a user to begin using a speech-based application immediately, without time-consuming speaker-specific training. However, recognition accuracy can be improved if such models can be adapted over time to individual speakers. This is another goal of my work. Thirdly, "pronunciation dictionaries" for automatic speech systems are still very much handcrafted. This process is both tedious and error-prone. I am interested in the process of automatically deriving such dictionaries from trainign data.

My other interests include the architecture and design of high-performance CPUs and multiprocessors, parallel algorithms and parallel programming.

The goal of my research is to dramatically boost the performance of future microprocessor-based systems. To accomplish this, we exploit various forms of parallelism through a combination of novel architectural, compiler and operating systems support. In particular, we have been focusing on the opportunities and challenges created by two important VLSI technology trends which are expected to reshape computer systems over the next decade: the potential for single-chip multiprocessing due to higher levels of single-chip integration, and the need to tolerate off-chip latency as the gap between processor speed and the speed of memory and I/O continues to widen.

Single-Chip Multiprocessing: The STAMPede Project.
As advances in integrated circuit technology continue to provide more and more transistors on a chip, processor architects are faced with the pleasant challenge of finding the best way to translate these additional resources into improved performance. One of the more compelling options is to integrate multiple processors onto the same chip. While this will certainly increase computational throughput, it will only reduce execution time of a given application if it can be run in parallel. Hence the key question is how do we convert the applications that we care about into parallel programs? Expecting programmers to only write parallel programs from now on is unrealistic. Instead, the preferred solution would be for the compiler to parallelize programs automatically. Unfortunately, compilers have only been successful so far at parallelizing the numeric applications commonly run on supercomputers. For single-chip multiprocessing to have an impact on the majority of users, we must also find a way to automatically parallelize the non-numeric applications (e.g., spreadsheets, web software, graphics codes, etc.) which account for the bulk of the software run on commercial microprocessors. Based on our preliminary studies, we believe that a breakthrough in our ability to automatically parallelize non-numeric applications may be possible through "thread-level data speculation", which is a technique that allows the compiler to safely parallelize applications in cases where it believes that dependences are unlikely, but cannot statically prove that they do not exist. To accomplish this, we add modest hardware support to track data dependence violations at run-time and alert the software so that it can recover appropriately. Developing the architectural, compiler, and operating system support necessary to turn this potential into a reality is the goal of the STAMPede (Single-chip Tightly-coupled Architecture for MultiProcessing) project.

Coping with Large Latencies.
Processor speeds are continuing to increase far more rapidly than off-chip components such as DRAM, disk, and networks, largely due to physical limitations such as distance and the speed of light. The challenge presented by this trend is that from the processor's perspective, the latency of main memory and I/O is increasing at a dramatic rate, and thus threatens to become an increasingly important performance bottleneck. The good news, however, is that the bandwidth of these off-chip devices has been improving through innovations such as synchronous (i.e. pipelined) DRAM, disk arrays, and fiber optic networks. Therefore we are exploring new ways that the compiler (with varying degrees of help from the hardware and the operating system) can use prefetching and other techniques to intelligently trade off consuming more bandwidth to reduce overall latency. Recent work in this area has included prefetching pointer-based codes, prefetching to hide disk latency in out-of-core numeric applications, and hiding network communication latency in workstation clusters.

Professor Nagle's research interests include architecture, embedded systems and reconfigurable computing. His primary research focuses on how careful architectural re-design throughout the system (hardware and software) can radically improve performance while greatly increase the functionality of computing systems. For example, the "Network-attached Secure Disk (NASD)" project is re-architecting traditional distributed storage systems to achieve a 10 fold increasing in system scalability. Unlike conventional approaches that fix assume either fixed hardware or software and focus on improving the other, NASD attacks both the software and hardware storage problems. Another project, "Software Defined Architectures", move processor and memory system management policy into the compiler which can more efficiently manage the underlying hardware.

I work in the general area of computer systems, specifically in the area of high performance distributed systems. The emergence of fast and low cost networks and desktop systems has created a new class of high performance computer systems that are also affordable and available. My students and I work on the general problem of how to program and use these powerful new distributed systems. My research approach is to understand and develop interesting new applications, and then to develop the software tools to support those applications.

For example, I work with civil engineers and seismologists on a Quake project that models the ground motion of the Los Angeles basin during earthquakes. The problems are so large (45 million unknowns) that they must run on a parallel or distributed system to get enough memory and cycles. However, a number of interrelated computer science problems must be solved before engineers and scientists can routinely run physical simulations on distributed systems. Here are some that I am working on and would love to pursue with new students.

Resource-aware distributed applications: To run efficiently on the new breed of high performance distributed systems, applications must become resource aware. They must determine the performance characteristics of the available resources and then make good decisions based on that information.

Interactive distributed simulations: Large physical simulations have always been computed in batch mode. High performance distributed systems should make it possible to escape from this "batch jail" and to run simulations interactively. For this to be possible, the entire simulation process, including the difficult visualization step, must be parallelized and run on the distributed system.

Parallelizing complex programs: Complex programs such as mesh generators are difficult to parallelize because they are large, complicated, and do a lot of pointer chasing. Yet mesh generation is a significant bottleneck in the physical simulation process and must eventually be parallelized. I am studying an approach for solving this problem based on thread-level data speculation on top of a software distributed shared memory.

Automatic library generation: As application libraries are asked to perform increasingly complex tasks on a wide variety of sequential and distributed systems, it is becoming difficult to provide collections of optimized, hand-written subroutines for every task. To address this combinatorial explosion of routines, I am investigating a technique called code composition that generates library routines from a small set of templates as application needs arise.

I am primarily interested in software architectures for user interfaces. In particular this involves studying how to structure user interface software so that pervasive capabilities are supported. Current graphical user interface architectures offer a pervasive capability to cut, copy and paste. These such pervasive integrating techniques allow the sum of the applications in the environment to be greater than the whole. There are few such capabilities beyond cut/copy/paste. We would like our graphical environment to have the richness of annotation, indexing, reorganization, multiuser interaction, distributed interaction and spreadsheet-like interconnections as part of the basic software environment rather than hand crafted in isolated applications.

My approach is to raise the fundamental model for interaction from one of processing events to one of manipulating information. The event model creates opaque applications which do not integrate well with each other. The application's true functionality is hidden from all but the human user. This requires all control of the application to be done manually. With an information model of interaction it becomes possible to support much more standard and pervasive functionality to all applications.

I am also interested in new software models for educational software. I would like to create a software architecture for education which is focused on interaction, creation and practice rather than media management and selection. I am interested in architectures which are not monolithic but rather support a variety of contributors and educational styles in an integrated and distributed instructional system.

I work in the area of human-computer interaction, primarily in the area of immersive and semi-immersive interfaces, sometimes called "virtual reality." I currently have a three-pronged research agenda:

Infrastructure.
My students and I have developed the Alice
rapid prototyping system for building interactive 3d graphics simulations. Alice is designed to be easy to learn in a short period of time, allowing the user to author desktop 3D graphics simulations, specifically concentrating on the real-time behavior of objects. Alice makes it possible to literally try hundreds of variations per day, and enables our collaborations with non-technologists, who need to be able to take a "what if" approach during the design process. Alice is currently distributed freely via the internet. We use Alice, augmented with tracking devices and immersive displays, to attack the other two prongs of our research agenda:

Fundamental Knowledge.
Fundamental Knowledge: working with perceptual and cognitive psychologists , we are addressing the question "When is Immersion Useful, and Why?" We expect that ten years from now, with different engineering tradeoffs to be made, Alice will be surpassed by something better. However, the knowledge we will gain regarding immersion is grounded in careful measurement of humans, whose biomechanical, perceptual and cognitive capabilities remain relatively constant over time. This work focuses on performing user studies to determine which aspects of immersion affect task performance. Our goal is to deduce general design principles, in order to produce a predictive theory regarding which real-world applications will benefit from immersive interfaces.

Interaction Techniques.
Virtual Reality is a new medium, just as film, radio, and Macintosh/MS-Windows-style "graphical user interfaces" (GUIs) are media. In the case of film and GUIs, there are well-acknowledged idioms of the medium (for film, flashback, crosscut, fade, etc., and for GUIs, scroll bars, pulldown menus, and the like). We are attempting to develop the lexicon of interaction techniques for VR.

Stage 3 Research Group

My primary current research interest is type theory and its application to language design, in particular in the areas of logic programming and functional programming. I am also working on educational applications of theorem proving tools and issues of human-computer interaction. I have further retained an interest in logic, automated theorem proving, formal program development, and programming environments.

Type Theory and Constraint Logic Programming.
Deductive systems are an important tool in the study of languages in Computer Science. Their applications include specification languages and their relation to implementations via proofs, type systems of programming languages, and structured operational semantics. Type theories, such as the LF Logical Framework developed by Robert Harper and others, allow the concise specification and direct implementation of formal deductive systems. I am developing a constraint logic programming language called Elf, based on the LF methodology. Elf is designed to quickly prototype metaprograms, such as theorem provers, type inference algorithms, or language interpreters by ascribing an operational interpretation to types in LF much in the same way that logic programming gives an operational interpretation to Horn logic. Higher-order equations of a certain form remain as constraints and are maintained during execution of a program. A prototype of Elf exists since Spring 1990 and has lead to a number of interesting discoveries and theoretical and practical questions which are subjects of ongoing research, such as efficient compilation, modular presentation of deductive systems, and support for the machine-assisted proof of meta-theorems. I am also working on issues of human-computer interaction and educational applications of Elf in the context of an introductory course in the theory of programming languages, in which all course material is fully implemented and proofs of meta-theorems fully checked. My recent work in the area of logical frameworks aims at incorporating linearity and increasing the degree of automation in the proof of meta-theorems.

Functional Programming.
Here my interest lie in the experimentation with extensions and refinements of type systems in order to increase the generality and precision of type information associated with programs. The primary questions in each case are the decidability and practicality of type reconstruction, and the amount of required explicit type information. Starting point is the type system of ML, a strongly typed functional language with an expressive module system. In joint work, I have investigated the addition of explicit polymorphism (so that more programs can be typed) and the introduction of recursively defined refinements of datatypes (so that more obvious programming mistakes can be caught by the type checker at compile-time). More recently, I have consider type systems for staged computation (including partial evaluation and run-time code generation) and the addition to dependent types to a ML.

My research involves using computational modeling, complemented by empirical studies, to investigate the nature of normal and disordered cognitive processing in the domain of reading and language. My modeling work is cast within a connectionist or parallel distributed processing framework, in which cognitive processes are implemented in terms of cooperative and competitive interactions among large numbers of simple, neuron-like processing units. These models provide new ways of thinking about how cognitive processes are implemented in the brain, and how disorders of brain function lead to disordersof cognition. I'm particularly interested in studying the effects of damage inconnectionist networks as a way of understanding the nature of cognitive impairments that can arise following brain damage, and in exploring ways of retraining damaged networks with the goal of helping to design more effective strategies for patient rehabilitation. I'm also interested in the implicationsof connectionist learning principles for the nature of normal and abnormal cognitive development.

Much of my work has focused on word reading, both in normal skilled readers andin brain-damaged patients with acquired reading disorders. My colleagues and Ihave developed connectionist models that exhibit many of the central characteristics of skilled reading, including the influences of word frequency and spelling-sound consistency on the time to pronounce words and the ability to pronounce word-like nonsense letter strings (e.g., MAVE) and to distinguish them from real words in lexical decision tasks. When the models are damaged invarious ways, they exhibit the major forms of acquired dyslexia, including "deep" dyslexia in which patients make semantic errors in reading aloud (e.g., misreading YACHT as "boat") and "surface" dyslexia in which patients produce regularization errors to exception words (e.g., misreading YACHT as "yatched").Moreover, retraining the damaged models yields patterns of recovery and generalization that are qualitatively similar to those found in cognitive rehabilitation studies, and generates specific suggestions for the design of more effective therapy for patients .

More recently, I have begun to extend my work to address other issues in language processing, including: 1) early language acquisition and the development of phonological representations through the interplay of speech comprehension and production; 2) semantic and associative priming effects in naming and lexical decision; 3) patterns of semantic impairments among brain-damaged patients, and their implications of the degree of functional specialization within the semantic system; and 4) sentence-level processing andthe interplay of syntax and semantics.

The goal of my work is to bring computer vision and robotics to the common man by creating systems that make the task of driving easier and safer. A key system requirement in the domain of driving is the ability to adapt to changing conditions, since the appearance of the environment around the car can change dramatically depending on environmental conditions and the type of road the car is on. My work and that of my students focuses on the development of learning techniques to achieve this flexibility.

Over 15 thousand people die on US roads every year in traffic accidents because they fall asleep at the wheel, or aren't paying attention and drift off the road. We are developing warning systems to prevent many of these accidents. Using a video camera to monitor the road ahead, we have developed systems that sound an audible tone, and optionally assumes momentary steering control, when the vehicle begins to drift from its lane.

We are also working on a research project called the Automated Highway System with the goal of improving safety and reducing congestion on our nations highways by fully automating the driving task. Key research issues in this domain are reliable perception of the vehicle's surroundings, and coordination of vehicle maneuvers such as lane changes and obstacle avoidance. Using the results of our research, we have demonstrated autonomous driving for long distances. One of our systems, called RALPH (Rapidly Adapting Lateral Position Handler) steered the Navlab for 98.2% of a trip from Washington, DC to San Diego, CA. When augmented with a millimeter wave radar for sensing obstacles, the system can detect vehicles ahead and automatically change lanes when appropriate.

My primary research interests are in the area of real-time and multimedia systems, specifically in the areas of multimedia and real-time operating systems, resource management techniques for predictable end-to-end timing behavior in distributed real-time and multimedia systems, and QoS-driven middleware services for these systems. My work is carried out in the Real-Time and Multimedia Laboratory.

Real-Time Mach.
The primary objective of Real-Time Mach is to provide a paradigm for predictable time and resource management in order to support distributed real-time and multimedia systems. This paradigm is supported by augmenting and extending the existing primitives in the Mach operating system. In addition, integrated real-time toolsets are provided to significantly enhance the understanding of the behavior of the systems being built. Real-Time Mach supports many primitives: real-time scheduling policies, real-time threads, synchronization mechanisms which bound and minimize priority inversion, real-time virtual memory management, resource reservation to guarantee sessions, and real-time communication protocols. Scheduler 1-2-3 and ARM (Advanced Real-time Monitor) are tools which work with Real-Time Mach for schedulability analysis and real-time monitoring of RT-Mach events. We are currently developing and distributing Real-Time Mach on a network of ix86-based workstations/laptops, and high-performance single board systems.

Real-Time Scheduling Theory.
The primary goal here is to develop needed technologies to build predictable networked real-time systems with end-to-end timing constraints. The project develops theory to analyze system timing behavior in precise mathematical terms, distributed real-time operating systems, real-time communications and networks, and automation support using tools. The philosophy of time management is based on fixed priority preemptive scheduling and in particular, rate-monotonic scheduling. This approach is currently adopted by many significant standards in real-time systems including POSIX, by many commercial operating systems with real-time support including Solaris, OS/2, Windows NT, AIX, etc. and has been used in many industrial and defense applications.

Dependable Real-Time Systems.
Many industrial application domains including aerospace, medicine, financial services, transportation, process control and manufacturing have stringent timing, high availability, safety and user-friendliness requirements. These widely varying and often contradictory requirements have forced the use of proprietary, conservative and/or inflexible solutions. The rapid advent of commercial processing and networking technologies has made little, if any, inroads into such industrial computing systems. This is primarily because such technologies often focus on throughput as the primary measure of quality. In industrial computing systems, on the other hand, raw throughput takes a secondary seat to the concerns of timeliness, availability and safety. This effort focuses on the system architecture, primitives (API) and implementation which are needed to support distributed networked systems which must meet both real-time and stringent high availability requirements. In particular, real-time scheduling theory is being married with dependability/high-availability techniques among other QoS-based metrics.

Raj Reddy's research interests include the study of human-computer interaction and artificial intelligence. His current research projects include speech recognition and understanding systems; collaboration on the web; universal digital libraries; and learning on demand.

My research centers on the design of programming languages and languages for specifying program behavior, mathematical tools for defining the semantics of such languages, and methods for proving that programs meet their specifications.

At present, my main interest is type theory. The last fifteen years have seen the discovery of a variety of type systems that have vastly enlarged our notions of what types are and how they might be used. My goal is to understand the semantics of these systems and to find a general concept of type of which they are all instances.

A second area of interest is the design, definition, and proof methodology of languages, such as Algol, that combine imperative constructs with a powerful procedure mechanism. This has led to the design of Forsythe, an extremely general and uniform Algol-like language that encompasses object-oriented programming.

Finally, I am trying to devise a functional programming language that gives the user control over the allocation and retrieval of storage. For this purpose, I am exploring languages with linear typing systems.

My current research interests lie in stochastic modeling of real world computational processes, particularly sequential processes, and in other machine learning paradigms, using tools from information theory, statistics, and artificial intelligence. The types of problems I am interested in include:

• Stochastic modeling of natural language for Human Language Technology applications, such as automatic speech recognition, machine translation, topic detection, information retrieval and textual datamining.

  I believe that the Computer Age will truly arrive only when computers learn to communicate with us humans on our own terms. For this to happen, we must pursue the four SILKy technologies: Speech, Image, Language, Knowledge. Human Language Technology (HLT) is the essence of the 'L' in SILK and is crucial for 'S' and 'K'. In my research in HLT, my tools are information theory and statistics. My raw materials are huge amounts of text of various types. My end products are new modeling techniques, improved performance of real systems, and new insights into the statistical nature of human language.

• Stochastic modeling of financial data. I am currently directing the Computer Science component of CMU's multidisciplinary Computational Finance program.

• Stochastic modeling of the behavior of large groups of people, such as patients, consumers and citizens. Through my activities in the Center for Automated Learning and Discovery (CALD), I have become interested in some of the vexing real-life learning problems faced by corporations, governments and other large organizations.

A Whole Sentence Maximum Entropy Language Model, Proc. IEEE workshop on Speech Recognition and Understanding, Santa Barbara, California, December 1997.

Statistical Language Modeling using the CMU-Cambridge toolkit. With Philip Clarkson. Proc. Eurospeech, September 1997 (ELRA Best Student Paper Prize).

A Maximum Entropy Approach to Adaptive Statistical Language Modeling. Computer, Speech and Language, 1996, Vol. 10, pp. 187--228.

The SPHINX-II Speech Recognition System: An Overview. With X.D. Huang, F. Alleva, H.W. Hon, M.Y. Hwang, and K.F. Lee. Computer, Speech and Language, 1993, Vol. 2, pp. 137--148.

Chaitin-Kolmogorov Complexity and Generalization in Neural Networks. With Barak Pearlmutter. In D. Touretzky, J. Moody and R. Lippmann (eds.), "Advances in Neural Information Processing Systems 3", San Mateo, CA: Morgan Kaufmann, 1991.

My research interests are in the areas of information visualization, artificial intelligence and cognitive psychology. I am especially interested in human-computer interaction for data exploration. Our students and staff are working on several projects within our research group and collaboratively on other projects in the School of Computer Science and industry, providing HCI and visualization expertise on multidisciplinary teams. Our projects are addressing:

• methods for applying artificial intelligence to automate creating effective visualizations of diverse information,
• novel techniques for human-computer interaction, including:
  • 3D visualization, navigation and manipulation;
  • interactive, graphical data exploration environments for navigation, aggregation, and transformation of data into useful information;
• automated explanation generation using coordinated graphics and text,
• interactive planning and scheduling environments for complex transportation and logistics systems.

SAGE: The SAGE project is studying issues in automatic and interactive design of graphical presentations of information. The goal of this work is to provide computer systems with the ability to communicate with users through the automatic design of graphical and textual displays. The rationale is to give users access to graphic design expertise and to reduce the burden of assembling data, designing displays and interacting with complex interfaces to graphics packages. To accomplish this, we have been developing an application-independent graphic design system called SAGE. As input, SAGE takes data from applications or databases and characterizations of the data and tasks to be performed. As output, it generates one or more displays which visually integrate the data in a way that supports the tasks. SAGE is currently being integrated with a suite of interactive tools within a data exploration environment called VISAGE.

Research issues in the SAGE project include:

• representing the syntax and semantics of graphical conventions;
• encoding graphic selection, composition and other design knowledge;
• developing techniques for searching the space of alternative designs;
• representing the behavior of interactive graphical objects for manipulating data in displays, especially for exploring and aggregating large data sets;
• coordinating automatic and interactive design processes (i.e., coordinating human and machine expertise);
• coordinating the selection and integration of text and graphics to support explanation of large data sets;
• creating new user interface environments that enable visualizations to function as user interfaces to complex systems;
• and developing approaches to dynamic redesign of displays to assimilate changing data.

3D Visualization and Human-computer Interaction.
Our research in 3D visualization is concerned with both new representation techniques as well as new interactive techniques for performing complex data manipulation and exploration tasks within 3D environments. We are developing a system called SDM (selective dynamic manipulation) which represents a new approach to interacting with graphical objects in visualizations. Users solve data analysis tasks by stretching, elevating, painting, and manipulating many visual properties of the objects that represent their data.

Research issues in the 3D visualization project include:

• creating new visualization metaphors for combinations of quantitative, geographic, temporal, categorical and hierarchical data;
• developing interaction techniques for a variety of input devices (e.g., pointing, selecting, linking, directing movement);
• 3D animation approaches;
• assessing human perceptual ability for assimilating 3D representations.

My research interests include: human-computer interaction, intelligent interfaces, automatic presentation design, explanation generation, data visualization, reading theory and speech based instructional software, and graphics.

Our research projects are: SAGE automatic presentation, VISAGE (graphical data exploration and manipulation, SDM (3D visualization & interaction), and AutoBrief (automated generation of text and graphical summaries and explanations of data).

The main focus of my research is in complexity theory and the foundations of cryptography. The wide applicability of the technical ideas in these two areas has allowed me to extend my work into learning theory, probability theory, and combinatorics.

I concern myself with the fundamental questions of each field: How can one obtain a separation result for interesting complexity classes? How can one reduce the security of a cryptographic protocol to the security of a simple primitive? What is a powerful inference method? How can one generalize probability theory to a theory where the events are almost independent?

I work most actively is the meta-theory of the above areas. This means questions like: What are the reducibilities among the above questions? What are the reducibilities among approaches to these questions? When are the perceived technical barriers to their answers related? When are they inherent?

I will mention two examples of these meta-theoretical results. Much of cryptography concerns the reduction of the security of complex protocols to the security of simpler ones. The most important question along these lines is whether a public-key cryptosystem can be based on a black-box, private-key system (such as the Clipper chip). Russell Impagliazzo and I showed that any proof of this particular reduction would contain inside it a proof that P Curiously, current approaches to the P v.s. NP question are themselves disguised forms of a problem in cryptanalysis. In order to prove that a function f is not in a complexity class C, the standard approach is to exhibit some combinatorial property of the function that provably prevents it from being in the class C. Alexander Razborov and I have argued that all the known lower bound proofs in circuit complexity use what we call Natural combinatorial properties. Any proof that uses a Natural property and shows that some function is not contained in a complexity class C, can be transformed into a successful cryptographic attack against any private-key cryptosystem which is implementable in the class C. Thus, these proof techniques cannot apply to classes (plausibly P, NC^1, or even TC^0) that contain unbreakable cryptography. A corollary greatly extends my previous work with Len Berman by showing that the restriction methods, which were so successful in showing AC^0 lower bounds, are essentially useless in resolving frontier questions in circuit complexity. At this time it remains unclear if proof methods which avoid Natural properties exist. Razborov has shown that in a weak fragment of arithmetic all proof methods are Natural in our sense; it follows under a cryptographic assumption that P v.s. NP is independent of this fragment. I have extended the notion of Natural property to that of NP-Natural property. This generalization also extends Razborov's independence result to more general (but still quite weak) proof systems.

My interests are in speech communication, machine perception, and human perception. My major interest is in the application of principles derived from the study of human communication to the design of speech understanding systems. Current approaches to speech recognition have attempted to engineer solutions for specific recognition tasks. The results have been impressive in the context of these tasks, but have contributed little to our understanding of the broader problem of speech understanding. A potentially better strategy is to examine in detail the performance of a system that has already successfully implemented a solution to this problem---the human listener.

My current work centers on the design of interactive systems using speech. Although speech appears to be the most natural communication modality for humans, its effective use for human-machine communication is not well understood. We are currently working to extend our knowledge in the following areas:

• The development of a theory of language design for speech-based interactive systems: Speech-mode communication predisposes the user to make certain word choices and to exhibit certain grammatical preferences. An understanding of these leads to better language design for interactive systems.
• Understanding the role of speech in the computer interface: Speech is an effective means of communication, but it is not always suitable for all types of interaction. The design of a speech interface takes place in the context of a task, of other available modalities and user preferences. We can approach this problem in a systematic way by developing an analysis interface appropriateness.
• Design of an environment that allow the automatic configuration of a speech channel for an interactive task, given an abstract specification of its capabilities.
• The study of human correction of misunderstandings and misrecognitions: People use certain conventions to recover from breakdowns in communication. These conventions can be transformed into heuristics that allow a speech system to automatically recover from recognition errors and more generally assume its share of channel maintenance duties.

My research interests focus on VLSI design automation. My principal interests are synthesis techniques to transform specifications into circuits, and geometric layout algorithms, including both design and verification problems.

Analog and Mixed-Signal Integrated Circuits.
The first reaction here might be "Why bother?" but the answer may be surprising. Advances in application specific IC (ASIC) technology make it possible to migrate entire systems onto a single IC. The problem: many real systems require some analog processing, and tools to synthesize these subsystems are basically nil. Telecommunications and robotics applications, vision and speech processing, local area networks (in particular, the network taps in the walls of every room at CMU), all interact with an analog environment and require analog circuitry. In the ACACIA project, we have been working on algorithms for high-level circuit synthesis and layout, and have succeeded in producing some real, workable analog ICs synthesized from specifications.

High-Performance Digital Systems.
Increases in the speed and density of digital systems have made it impossible to ignore some low-level performance concerns like wire delay. The challenge here is transforming these nasty details into clean abstractions for combinatorial algorithms to attack. Projects here include placement and routing for very large very fast chips, clock tree design, and synthesis tools for field programmable gate arrays. 3-D Package Design. There are lots of algorithms for arranging the components on the 2-D surface of an integrated circuit, surprisingly few for arranging the components of a mechanical design, like a wearable portable computer or the packing of cargo in a space shuttle cargo bay. I've been working with mechanical engineers to translate 2-D VLSI algorithms into 3-D "product layout" applications, and have unearthed some nice new algorithm-design problems worth working on.

The focus of my research is a single problem, defined by the following question: "How does one share information safely and efficiently in a distributed computing system shared by a large number of users, many of whom may be mobile?"

This is a problem of fundamental importance, because access to shared data is critical for effective collaboration in a geographically dispersed and mobile user community. In pursuing this goal, I often have to address subproblems in areas such as network communication, security, reliability and performance evaluation. As an experimental computer scientist, my style of research involves the design, implementation and evaluation of systems with ambitious goals.

The advent of compact, powerful portable computers and wireless communication technology has created the new field of mobile computing. A key requirement of mobile computing systems will be the ability to access critical data regardless of location. The research issues induced by mobility on data access form the focus of my current research efforts.

I am working on the design of a platform for mobile computing called Odyssey. A key architectural attribute of Odyssey is that it allows application-aware adaptation to changing environmental conditions. This is in contrast to insulating applications completely from the effects of mobility. I believe that controlled exposure of mobility to applications will allow them to better cope with the effects of mobility.

Work on Odyssey is proceeding in parallel with the final phases of work on its predecessor, the Coda File System. Coda has proved to be an excellent entry point into the world of mobile computing. Its support for disconnected and weakly connected operation is a key enabling technology for the field.

My research is in two areas-program manipulation tools and information structures for collaboration. I focus here on the Fluid Architecture project, which is in the first of these areas and involves the use of program analysis and manipulation techniques to support program development and evolution. Please feel free to come talk to me about any of these ideas, or about my research in computer-supported cooperative work (which is not covered here).

All programmers face the difficulty of having to make small-scale structural design decisions very early in the software process, well before the consequences of those decisions can be understood. For example, having decided to include an integrity check for a parameter, should the check be done at the procedure being called or at all calling sites? Which site is selected (or whether code is replicated in order to have it both ways) determines which optimization opportunities can be exploited, and is best decided later in the process. And in practice, once these small structural commitments are made, particularly in the design of an API, they can be very difficult to revise. My research hypothesis is that this brittleness is not a necessary attribute of software, and that semantics-based program analysis and manipulation techniques can offer a way for programmers to retain structural flexibility.

Program manipulation techniques of the sort we are exploring can also be used to adjust data representations or make other changes that require potentially pervasive alterations to code. A simple representational change to Java strings, for example, requires simultaneous changes to more than 80 methods. Practicing programmers can devote considerable effort to this "bureaucratic" business of organizing and reorganizing internal interfaces and encapsulations, maintaining and revising representation and control invariants, and managing response to exceptional conditions. Most of the time they are working with existing code.

I am interested in program analysis and manipulation techniques that can be embodied in tools that programmers can use easily for routine program evolution of this sort. For such tools to be practical, programmers must not have to write extensive specifications of program functionality or architecture. Also, the tools must be interactive, enabling software engineers to explore a space of possible design approaches and to explore multiple structural views of a system. To this end, we are are designing experimental tools for analyzing and manipulating Java programs.

My work in logic has mainly been in the areas of model theory, automata, set theory, modal and intuitionistic logic, constructive mathematics, and connections between category theory and logic. Philosophical interests concern the foundations of logic, the philosophy of mathematics, and the semantical analysis of natural language. Work in computer science has been directed to the development of denotational semantics of programming languages and the mathematical foundations of a suitable theory of computability. Current projects aim at unifying the semantical approach with constructive logical formalisms to be able to give rigorous and machine-implementable proof methods and development tools for the "inferential" construction of correct programs. Very recent research with current graduate students aims at combining categories of domains with traditional categories of mathematical structures and studying the computability and type theory that results. Another recent strong interest is in using methods of symbolic mathematical computation (computer algebra).

Image-Based Modeling and Rendering.
A central problem in computer graphics is producing images that appear photographic, thereby fooling people into believing they are viewing a real scene. While rendering techniques have advanced dramatically in recent years, we are still far from this goal of photorealism, largely because of the difficulty of constructing realistic 3D models. We propose to solve this problem by "importing" real-world objects and scenes from photographs and paintings. Towards this end, we are developing two classes of techniques, based on image morphing and 3D reconstruction, respectively. The first approach rearranges pixels in a set of input images in order to produce images of the scene from different camera viewpoints. This view morphing approach enables effects such as rotating a person's head in 3D from one photograph. We are also investigating voxel-based 3D reconstruction techniques to solve larger-scale visualization problems, such as producing building walkthroughs and flybys of complex landscapes by processing images from video camcorders.

3D Augmented Video Editing.
Imagine trying to remove a moving figure from one video sequence and paste it into another. While simple to describe, this operation is extremely difficult to achieve because of the need to manually trace moving contours in in every frame of an image sequence. The goal of this project is to develop video editing tools that blend user-interaction with computer vision techniques in order to manipulate entire video sequences by touching only a small number of frames. In addition to cut-and-paste operations, we are interested in 2D Photoshop-style editing operations that propagate (e.g., applying lipstick to a moving face by painting it into a single frame) as well as 3D effects like changing camera viewpoint and illumination conditions.

Software now accounts for the the lion's share of the cost of developing and using computer systems. My research is directed at establishing a genuine engineering discipline to support the design and development of software systems. Currently I'm working on design methods, analytic techniques, and notations for building complete software systems out of subsystems and their constituent modules. This is the software architecture level of design, which makes me a software architect.

Software designers often describe the architectures of their systems by referring to common patterns such as "pipe and filter systems", "client-server systems", "layered systems", and "object-oriented systems". They use box-and-line diagrams to explain the system organizations. Most of these descriptions are highly idiosyncratic and ad hoc; nevertheless, the designers manage to communicate.

People talk about a world in which software systems are developed by taking components off the shelf and hooking them together, "just like Tinkertoys". In fact, though, software components interact in many different ways -- via procedure calls, pipes, signals, shared data, etc. So the situation is more like grabbing parts at random from a bathtub full of Tinkertoys, Lego blocks, Lincoln logs, Mechano parts, and so on -- then expecting them to fit together in some sensible way. (Actually, it's more like taking parts at random from a landfill, but that's a different story.)

The Vitruvius project is developing theories, notations, and design strategies to make good software designers' ad hoc knowledge visible, precise, and subject to analysis. An initial prototype, UniCon, can describe a range of systems that rely on a variety of component interaction strategies. It can create wrappers to convert code to support certain kinds of interactions. We have recently reorganized it to simplify adding new connectors.

Organizing informal design guidance into well-grounded theories brings us closer to an engineering discipline for software. We follow a strategy of progressive codification -- we begin by capturing informal knowledge as carefully as possible, then make the descriptions more formal as we come to understand it better.

We want to be able to propose architectures for software in terms that other software engineers found comprehensible; we want to compare software organizations on an analytic basis; we want to convey knowledge of software structures more effectively to a maintainer or developer. In short, we could reuse knowledge of software organizations and particular software artifacts in reasonable ways.

Examples of research questions that interest me include:

• Notations and tools for software architecture: Identify or develop notations that are appropriate for describing system construction from components. What are the primitive elements and operations? What are the useful abstractions? What is the analog of the abstract-data-type abstraction function, which demonstrates that a component implements the interface abstraction it specifies?
• Taxonomy of styles and elements: Develop classifications of architectural styles and of the components and connectors that are used to create systems in these styles. Find ways to identify components that are used in mismatched ways and to correct the mismatch if possible.
• Consistency of views: When multiple different views (e.g., data flow and state transitions) are used in a design, how do you check their consistency?
• Interoperability: Architectural definitions may specify incompatible combinations of components. For example, the unix sort filter computes "the same" thing as the system call, but the two are not interchangeable. Check the definitions for consistency (under whatever specifications are provided). When inconsistencies are found, reconcile them if possible or report detailed nature of mismatch.
• Design guidance: Organize information about a class of systems to help the software developer make design decisions. Usually there are multiple architectural alternatives; how do you choose among them? How does information about the application you're constructing influence the design decisions?
• Partial, incremental specifications: Conventional doctrine says that specifications are fixed, complete, and homogeneous -- they capture everything there is to know about a component. In fact, however, they are intrinsically incomplete: you can't anticipate every property another component might depend on. They are incremental: as you learn more about a component, you must capture it. And they are heterogeneous: different properties require different notations. How do notations and tools have to change to cope with the difference between doctrine and reality?
• Establish analysis techniques: Identify properties such as system throughput that are appropriately specified and analyzed at the architectural level rather than the individual-component level. How do you specify and analyze them? How do you derive specifications for individual components that guarantee the system properties?
• Evaluate usability: Determine how useful the prototype system is for software designers.

My major interest is in the modular design and rapid prototyping of reliable computing structures. Three research projects support this interest: Mobile Computers, Concurrent Design, and Reliable Systems.

Mobile Computers.
The information processing industry is undergoing a paradigm shift. In the 1960's information processing was concentrated in mainframe computers operated by central staff and accessed by custom-built programs executed in batch mode. By 1970 the invention of the time-sharing operating system allowed users to interact with information on-line. However, time-sharing systems were still centrally based with most of the computing cycles devoted to information manipulation rather than the human computer interface. With the advent of the personal computer in the early 1980's a substantial portion of the computing power could be dedicated to the single user. We have completed ten generations of wearable computers. Navigator 2 records sheet metal defects onto a two-dimensional model of the aircraft. Speech recognition and a head-mounted VGA display allows the aircraft inspector to enter information hands-free. Metronaut is a light weight, low energy (eg. one pound, one watt) multi-media information system allowing collaboration via wireless communications. Current efforts also include a family of smart modules for speec-to-text, text-to-speech, language translation, and optical character recognition.

Concurrent Design.
The goal of the project is to support the generation of designs from high level systems specifications into completely assembled electronics, mechanical, and software systems. The goal is to reduce design time by 1 to 2 orders of magnitude. The Concurrent Design methodology has been used in all ten generations of mobile computers described above. Groups of up to 30 designers representing up to five disciplines designed and fabricated multiple copies in less than four months, and developed tools to support the concurrent design process. For all levels of design there are common issues that must be addressed including design data bases, design information representation, human-computer interfaces, simulation/validation/ verification, automatic synthesis, test generation, and design selection criteria. MICON is an example of a synthesis tool which supports concurrent design. MICON is a knowledge-based system which produces parts lists and netlists from high level specifications in a matter of minutes. Design objective include cost, area, performance and reliability. MICON is trained about new design situations using a knowledge-acquisition front end coupled with a convention logic schematic capture program.

Reliable Systems.
For over two decades, computer system design and evaluation has been based upon performance benchmarks. Comparable benchmarks do not exist for evaluating the quality and robustness of computer hardware/software systems. This project is developing a family of portable benchmarks for a variety of operating systems and programming language environments. The benchmarks are based upon over a decade of experimentation with fault injection including the next generation air traffic control system. To date, fault-tolerant systems have been custom designed. We are developing technology enabling the construction of reliable systems from commercial-off-the-shelf (COTS) hardware and software. One approach is to add middleware between the applications software and the operating system. Sentries can perform error detection, data logging, and automatic retry, all transparent to the application software. Transparent journaling and checkpoint/retry have been demonstrated. Other research issues include automatic: generation of assertion checks, checkpointing/rollback, and redundancy through replication. Studies indicate that the majority of system downtime is due to human errors in either design or operation. This project explores the design of software systems and interfaces to reduce human errors. Research is in cooperation with Maxion and Koopman.

My research interests focus on artificial intelligence, primarily in the areas of highly autonomous systems (especially mobile robots) operating in rich, uncertain environments. This necessitates robots that can plan, effectively reason about uncertainty, diagnose and recover from unanticipated errors, and reason about their limitations. In particular, I am interested in architectures for autonomy that combine deliberative and reactive behavior, probabilistic and symbolic planning, and reliable execution monitoring and error recovery. The goal is to create intelligent systems that can operate autonomously for long periods of time in unstructured, natural environments.

Highly Autonomous Systems.
We are investigating methods for making mobile robots more robust and self-reliant. We are exploring the use of model-based reasoning techniques to detect and diagnose failures, hierarchies of monitors and exception handlers to catch unanticipated situations, and learning of new monitors and exception handlers from experience. The research incorporates symbolic (model-based) reasoning, probabilistic reasoning, interleaving of planning and execution and selective monitoring of relevant environmental features. We are also investigating social interaction between robots and humans, and reliably completing complex tasks (fax delivery, exploration). Testbeds include Xavier and Amelia (office-delivery robots), Nomad (Antarctic exploration rover), and NASA's next Mars Rover.

Architectures for Autonomy.
We have developed the general-purpose Task Control Architecture (TCA) to support distributed planning, execution, error recovery, and task management for autonomous systems. TCA has been used in over a dozen mobile robot projects at CMU and elsewhere. Current research is developing the Task Description Language (TDL), an extension of C++ that includes syntax to support task-level control, and is investigating using formal models to verify robot control systems. To date, we have developed tools for visualizing message traffic, task decomposition, and plan execution. Testbeds include Xavier (indoor mobile robot) and autonomous interplanetary spacecraft (NASA).

Multi-Robot Coordination.
We are researching issues of how multiple, heterogeneous robots can cooperate to carry out high-level tasks. Issues include having the robots negotiate which tasks they will achieve, and when, monitoring each other's performance, and adapting dynamically to changing situations. Testbeds include the Mercator project (urban exploration robots) and multi-robot assembly and construction.

Probabilistic Planning and Reasoning.
We are exploring advanced planning and reasoning techniques, many of which involve probabilistic reasoning. In particular, we are exploring issues of determining when to plan and when to act, in order to optimize the total time spent solving problems, and using partially observable Markov models to navigate robots in office environments.

I am interested in AI, especially the use of computers to simulate human thinking, discovery, and learning processes. At present, most of my research effort is directed to four areas.

Programs that Discover Scientific Laws.
During the past decade, I have been engaged with colleagues in studying the psychological processes that are involved in original scientific work, and in building computer programs that simulate the processes of scientific discovery. In 1987, MIT Press published Scientific Discovery, describing the first products of that work, including BACON, GLAUBER, STAHL, BLACK, and DALTON. Most of the work already completed has been concerned with discovery achieved inductively from data, but including the invention of new concepts and including some search guidance from prior theories. The systems are capable of rediscovering a considerable number of scientific laws and concepts of first magnitude.

Now the work is moving on to other aspects of scientific discovery, especially the processes that guide an experimental program and the design of experiments and the processes that develop and adapt appropriate problem representations. Work with Deepak Kulkarni has produced a computer program that simulates Hans Krebs' course of discovery of urea synthesis in living tissue. Work on representations, and especially diagrammatic or pictorial representations, is continuing. Wei-min Shen modeled a system capable of discovering hidden variables (variables not directly observable) to explain the behavior of a complex system (e.g. Mendelian genetics). Raul Valdes-Perez built a program for elucidating the paths of chemical reactions. Eugene Fink is working on the theory of representation change.

Modelling Expert and Novice Skills.
In collaboration with colleagues and students, I have been studying the behavior of novices and experts in various problem domains, especially physics and economics. The aim is to simulate novice and expert behavior, and use these programs to guide the construction of learning programs that will turn a novice into an expert. These explorations are leading to interesting discoveries about the role of representations in problem solving, and we plan to extend them to a broader range of domains, such as chemistry and molecular biology.

Learning Programs.
Adaptive production systems learn by solving problems by trial and error, then learn more powerful techniques from their experience; or they learn by analyzing worked-out examples of problem solutions. These are very powerful techniques and the surface has just been scratched. There are obvious possibilities of application to automatic programming. The results of earlier research (the dissertation of David Neves) have been applied to the construction of an algebra and geometry curriculum for human students that enables them to learn the subject from worked-out examples and problems, without lectures or textbooks. The curriculum is now being used successfully in a number of schools in China. This work has many implications for tutorial systems and computer-aided instruction, which I shall begin to explore.

An important issue is the distinction between a program that learns by rote and a program that learns with understanding, and the implications of this distinction for retention of what is learned and the ability to transfer learned skills to new tasks.

Diagrammatic Representations and Imagery.
The use of diagrams or other kinds of pictorial displays greatly facilitates problem solving in many domains. In the light of this fact, we have been exploring the function of diagrams in problem solving and the kinds of computer representations that will reap the same computational advantages that paper-and-pencil diagrams or CRT displays provide for humans. Programs have been constructed that demonstrate the value of diagrams in specific domains (e.g., pulley problems in physics, geometry theorems). Most recently we have been investigating how diagrams facilitate understanding of special relativity and of economics, and have built a simulation of the "Mind's Eye" and its processes for interpreting diagrams. We intend to develop the work in several directions: first, to examine a much wider range of examples of the use of diagrams; second, to explore the implications for computer graphics; third, to investigate how new representations, diagrammatic or other, can be generated; and fourth, to study the relation between diagrammatic and propositional representations.

I have worked in a variety of different areas of computer science, including amortized analysis of algorithms, self-adjusting data structures, competitive algorithms, natural language parsing, computer game playing, synthesis of musical sounds, and persistent data structures.

Natural Language:
I (jointly with coauthor Davy Temperley) wrote a parser for English. The system (which we call a link grammar) is unlike phrase structure parsing or context free parsing. The scheme is elegant and simple, and our grammar captures a very wide variety of complex phenomena in English. We (John Lafferty and I) plan to use this as a basis for a new statistical model of language. This work on language is described in two technical reports: CMU-CS-91-196, CMU-CS-92-181.

Competitive Algorithms:
Consider the idealized problem of deciding whether to rent or buy skis. You're about to go skiing. The cost of renting skis is $20, the cost of buying them is $400. Clearly if you knew that you were going to go skiing more than twenty times, then you could save money by immediately buying skis. If you knew that you would go skiing fewer than twenty times, the it would be prudent to always rent skis. However, suppose that you can not predict the future at all, that is, you never know until after one ski trip ends if you will ever go skiing again. What strategy would you use for deciding whether to rent or buy skis? Your goal is to minimize the ratio of the cost that you incur to the cost you would incur if you could predict the future. (Hint: you can come within a factor of two.)

Since the simple principle behind this example turns out to be very useful we have given it a name. A competitive algorithm is an on-line algorithm (it must process a sequence of requests, and it must process each request in the sequence immediately, without knowing what the future requests will be), whose performance is within a small constant factor of the performance of the optimal off-line algorithm for any sequence of requests. (In the skiing example, there is only one type of request, and the only uncertainty is in knowing how long the request sequence will be.)

My collaborators and I have discovered a surprising variety of practical problems for which there exist very efficient competitive algorithms. We have also developed a partial theory of competitive algorithms. However there remain many interesting open problems, from discovering competitive algorithms for specific problems, to answering general questions about when such algorithms exist.

Data Structures:
Data structure problems are typically formulated in terms of what types of operations on the data are required, and how fast these operations should take place. A worst-case analysis of the performance of a data structure is a bound on the performance of any operation. An amortized analysis of a data structure bounds the performance of the structure on a sequence of operations, rather than a single operation. It turns out that by only requiring amortized efficiency (rather than worst-case), a variety of new and elegant solutions to old data structure design problems become possible. My collaborators and I have devised a number of such solutions (splay trees, skew heaps, fibonacci heaps, self-adjusting lists, persistent data structures, etc.), and I continue to have a strong interest in data structures and amortized analysis.

Interactive Network Games:
I wrote and maintain the internet chess server. This very popular service allows people from all over the world to play chess, observe others playing, and communicate with each other in various ways. A rating is computed for each player as a function of his or her performance. You can try it yourself with "telnet ics.uoknor.edu 5000".

Principal research interests lie in the theory of computation with special emphasis on symbolic computation. In particular, current research involves lambda calculus and combinatory algebra. This area underwent extensive development in the first half of this century, and then lay dormant until Dana Scott's fundamental work in the 1970's. Part of what has emerged from Scott's work is that lambda calculus forms the foundation of functional programming at both the semantic and syntactic levels. The area has been revived by an influx of theoretical problems directly related to design and implementation issues.

My research interests are in the areas of computer networking and distributed systems. I am specifically interested in developing techniques that make networks significantly more useful to applications. While some improvements in network technology do not depend on how the network is used (e.g. incremental improvements in link bandwidth), many optimizations depend on the application's communication behavior. For example, some optimizations exploit properties of application traffic (e.g. inherent bandwidth limits of multimedia traffic, temporal locality in traffic destinations). A more extreme example is network features that address specific application needs (e.g. quality of service, application-level congestion avoidance), and that require the network and application to explicitly collaborate to improve performance. As a result, my research often involves collaboration with network users, allowing me to better understand their problems and to evaluate results. This type of collaboration is becoming more important as applications use the network more aggressively.

Improvements in application-level network performance come in many forms and benefit a wide range of applications. Examples include increasing throughput and reducing latency (e.g. for distributed high-performance computing applications), making network performance more predictable (e.g. for multimedia applications), optimizations across multiple "cooperating" traffic streams (e.g. in video conferencing or parallel file systems), information exchange between the network and the application (e.g. in support of network-aware applications), and quality of service guarantees (e.g. for high quality electronic services). Because of the wide diversity of network optimizations, my research touches on many areas of computer science. For example, optimizing throughput requires optimizations in the architecture, operating system, and protocol implementation of the sending and the receiving computer systems. Supporting a new quality of service class, on the other hand, requires the development of new protocols and resource management algorithms.

In the last 10 years, I have worked on several high-performance networking projects that focused on dramatically increasing the throughput and reducing the latency between workstations and PCs. These projects include Nectar, the first "network of workstations" built around a high-speed switch-based local area network, Gigabit Nectar, a metropolitan area network that allowed workstations and supercomputers to communicate at 100s of Mbit/second using standard communication protocols (TCP/IP), and Credit Net, an OC-12 (622 Mbit/second) ATM network that supports a variety of protocols for traffic management. These projects used a variety of techniques such as data copy avoidance, hardware checksumming, application device access, and protocol specialization to optimize communication performance. All three networks were used extensively by applications in diverse areas such as environmental modeling, remote medical consulting, engineering design, circuit simulation, and medical image processing.

I am currently working on the Darwin project. The goal of Darwin is to define, implement and evaluate "application-aware" resource management mechanisms for networks. The idea is that given the wide diversity in network applications, networks will have to be able to support quality of service models that can be customized by applications. This is achieved by letting the application participate in resource management, so that network resources are applied in a way that is most effective for the application. Application-awareness is a very general technique that will have an impact on many areas of networking. For example, it can form the basis for sophisticated quality of service models for multiparty applications that combine many different types of data streams. Other problems to which application-awareness can be applied include the generation of feedback for network-aware applications (e.g. for multimedia data streaming), customizable reliability support, dynamic short-term reservations, the implementation of high-quality multimedia network services, and improving network performance for mobile and wireless hosts.

My research interests involve a number of topics joined by the common threads of signal processing, sound, and acoustics. At present I am most actively working on topics related to automatic speech recognition and signal processing in the auditory system. I have also been involved in projects in the areas of biomedical instrumentation, particularly with regard to the auditory system, physical acoustics, computer music, and computer-aided instructional systems.

Automatic Speech Recognition.
The SCS speech group is developing speech technology that can perform unlimited-vocabulary speech recognition on a speaker-independent basis under difficult acoustical conditions. We are also developing practical applications that make use of spoken language interfaces to perform useful tasks.

The major goal of my own work speech research is to enable CMU's SPHINX recognition system to become as robust to changes in acoustical environment and ambience as it is to changes in speaker. In particular, we must deal with problems in recognition accuracy resulting from additive noise sources, background music, competing talkers, change of microphone, and room reverberation. We are developing several different types of solutions for these problems including improved noise cancellation and speech normalization methods, the use of representations of the speech waveform that are based on the processing of sounds by the human auditory system, and the use of arrays of microphones to improve signal-to-noise ratio. In previous knowledge-based speech-recognition systems I had also worked on statistical classification, speaker adaptation, and the integration of syntactic, grammatic, and semantic information.

Signal Processing in the Auditory System.
The general goal of this research has been to develop a better understanding of how the auditory system processes sound, to apply this knowledge to the treatment of various kinds of hearing impairments, and to apply this knowledge to the development of more robust speech recognition systems. I am presently carrying out psychoacoustical measurements of various aspects of monaural and binaural perception, and developing models based on communications theory and linear system theory to relate the results of these experiments to neural coding of sounds by the auditory system. Most of my work in hearing has been concerned with the localization of sound and other aspects of binaural perception.

My research covers a variety of topics relating to compilers and programming tools for high performance computers, including parallel and network computers. The main projects I am currently participating in are as follows:

Remulac (Programming network aware applications).
The networks connecting computers are becoming faster and more sophisticated but programming of network applications continues to be ad-hoc and primitive. The goal of the Remulac project is to support the development of applications that need advanced features of modern networks like resource reservations and quality of service guarantees. The dramatic increase in the use of network computing makes it very important that the network resources be managed efficiently and that resource intensive applications be able to adapt to changing network conditions. The integrating component of this project is a common language for applications to query the status of a network dynamically. The major research challenges are collection and management of changing network traffic conditions and support for adaptive execution based on the availability of computation and communication resources.

Fx (Integrated task and data parallelism).
The Fx compiler for parallel computers integrates the paradigms of task and data parallelism. This gives the user considerable programming flexibility, allowing the expression of most common parallelism structures including data parallel pipelines and parallel divide and conquer. An important result is that this model leads to good parallel performance on many applications that are considered difficult for efficient parallelization. For example, in the areas of digital signal processing and image processing, this approach is able to overcome the low scalability due to small data sets like images, and for scientific applications that involve continuous I/O, the techniques are used to hide the I/O bottlenecks. As part of this research, we have discovered the key relationship between efficient execution and program mapping and exploited it to automatically determine the optimal mappings of parallel programs.

Compiler directed migration.
Internet is a massive pool of information and computing resources, but effective use of internet resources often requires programs that can migrate to resources on demand. The focus of this research project is to support program migration in a general way, i.e., to support migration across heterogeneous computers and across different optimization levels. Potential applications include web search engines, mobile computing, information servers, and compute servers. In order to support migration and restart, the program state is collected in terms of the execution context in the source program and relevant source program variables. This leads to natural support for heterogeneous migration which is difficult to support with simple checkpointing. This research will build on the technology developed for debugging optimized code and examine the tradeoffs between optimization and migration support.

I am interested in AI, machine learning, artificial neural networks and robotics.

Machine Learning.
A primary goal of my research in machine learning is to contribute to the development of learning algorithms applicable to complex real-world tasks, particularly when training data is expensive to obtain. Despite the enormous complexity of the "real world," humans often generalize strikingly well even after having seen as few as a single training example--a capability currently unmatched by computers. My research on lifelong learning assumes that a learner encounters a whole collection of learning tasks over its entire lifetime. When learning a new task, a lifelong learning algorithm may re-use what has been learned in previous learning tasks. Key questions that arise in the context of lifelong learning are how to learn, represent, and transfer general-purpose domain knowledge across related learning tasks. In my recent PhD thesis I have developed several approaches that can accumulate and transfer domain knowledge, hence generalize better from less training data.

Robotics.
My core interest in robotics is robot learning. For robots to be truly autonomous, they must have the ability to adapt to unforeseen situations, and to improve with experience. In the past, I have applied various learning techniques to mobile robot perception and control. I am currently designing a unified robot learning architecture, and to explore principal ways for robots to interact with humans more naturally.

My current research activities are in the area of computational neuroscience and robot learning.

Neural Models of Animal Navigation.
How do animals represent space in their brains? In rats, ``place cells'' in the hippocampus fire when the rat is in a particular location. The firing fields of place cells are controlled by distal landmarks (e.g., they rotate when the landmarks are rotated), but they also persist (and the animal can navigate effectively) when the lights are turned out. Elsewhere in the brain, head direction cells in thalamus and postsubiculum fire selectively when the animal faces in a particular direction, and place fields have recently been shown to drift in synchrony with the head direction system. In addition, there is evidence that rodents perform path integration, combining vestibular cues and motor feedback to generate a running estimate of their coordinates in some reference frame. Using data from a variety of animal behavioral studies, my students and I are developing a neural network model to replicate the navigational properties of rodents. The goal is to have a single, unified architecture that deals with a broad range of navigation phenomena, including open-field tasks, proximal landmark-based tasks, and radial arm and Hampton Court type mazes. With this work we hope to shed light on the algorithms rodents are using, and the roles the hippocampus and other brain areas play in navigation. In addition, we are collaborating with Bill Skaggs of the Department of Neuroscience, University of Pittsburgh, on neurophysiological investigations of the hippocampal and head direction systems.

Robot Learning by Operant Conditioning.
Animals can be taught to perform complex tasks by a conditioning technique that reinforces desired behavior with a reward. This is how animal performers are trained, and seeing eye dogs as well. Through a process called shaping, complex behaviors can be built up gradually by shifting the reward policy as the animal progresses in learning the task. With the right learning algorithm, this training procedure should also be applicable to robots. Some students and I are exploring this idea and implementing our operant conditioning learning algorithm on Amelia. Current thinking in cognitive neuroscience is that there are several different memory systems involved in learning, e.g., hippocampus, amygdala, and striatum. By building a working model of operant learning, we hope to better understand the implications of this theory.

Can we buy and sell items over public networks? Finding methods to support electronic commerce forms a major thrust of my research. I use tools from distributed systems, computer security, cryptography, protocol theory, applied algorithms, and applied economics to realize electronic commerce.

Central to my investigations is the idea of atomicity: I am interested in making financial transactions atomic and also making delivery of information atomic -- we deliver information if and only if a customer is paid.

Together with my students and colleagues, I am engaged in several major projects exploring electronic commerce and computer security. (A longer description can be found off my research plans on my web site.) I am always happy to discuss these projects or any research question. Please feel free to come and talk to me anytime:

Auctions with Private Bids.
We are building systems for light-weight, high-security auctions. These auctions can support very low overhead, naturally fit into an active network approach, and can protect the privacy of the bidders who place bids. (In economic terms, our auctions support the economic efficiency of English auctions, the computational efficiency of sealed-bid auctions, and the privacy properties of Dutch auctions.) We also believe that these auctions can be used to mediate the survivability of systems by allocating scarce resources.

Dyad.
We are building secure coprocessors that use physical mechanisms to protect memory. If the processor is breached, then all memory is erased. We have ported an operating system onto the secure coprocessor and can run secure remote execution routines on the secure coprocessor. Our work points the way to secure electronic wallets. Fundamental research questions include: how does one conduct an electronic negotiation? How does one form an electronic commerce contract?

NetBill.
We are building an billing server that can be used to charge information purchases over the internet. Unlike credit cards, which have a marginal transaction cost of twenty-five to sixty cents per purchase, NetBill has a marginal transaction cost of under one cent. Fundamental research questions include: How does one support various pricing schemes in this approach? How can one provide a sealed proof of the transaction? How can one support certified delivery so that customers are charged exactly when they receive material? Is it possible to mark documents with low-level dithering codes that uniquely identify the documents and will discourage illegal pirating of copy-written material?

Electronic Franking.
The US Postal Service detects losses of over 200 million dollars a year from people who use bogus postage meters or just rubber stamps to print postage indicia. We have been investigating new standards involving cryptographic methods and 2-D bar codes for computer generated postage indicia. USPS has announced their intention to use a variant of our standards starting in a year. Based on our work, a number of international post offices are also moving towards similar standards. It is the goal of this work to support more general forms of electronic commerce than merely supporting mail. Fundamental research questions include: How does one protect against copying (with a computer) postage indicia on mail. How does one support hand scanning of mail? Can we make postage stamps unforgeable? Can we make other documents (such as passports) unforgeable? How does one protect the privacy of senders and recipients of mail in these schemes?

User Interfaces for Computer Security.
The most common failings of computer security arise not from bugs but from user errors. In many cases, those user errors directly result from bad user interfaces. Computer security interfaces are especially challenging since little feedback is provided (and so a user may not realize there is an error until too late) and since once information is released, it may be impossible to undo the effects (closing the barn door after the cows have left.) Moreover, in distributed computing scenarios, all users are responsible for computer security -- including unsophisticated users.

NB: Starting in Fall 1998, I will be on leave to the University of California, Berkeley where I will have a joint appointment as Professor in the Department of Electrical Engineering and Computer Science and the School of Information Management and Systems.

One measure of the fundamental character of a scientific problem is the interest it attracts outside the discipline. A fundamental CS question of wide interest is: what can computers ultimately do? On the research frontier is the question of whether high-end tasks of human creativity can be automated. My main interest is creative discovery in science and related areas.

Together with a variety of collaborators in CS and natural and social science disciplines, we focus on developing algorithms to partially automate high-end reasoning tasks that lead to the discovery of new scientific knowledge. We also spin off practical interactive software to enhance the work of researchers by making conclusions faster and more reliably. Research on computational scientific discovery enjoys the benefits of simultaneously being on frontiers of AI research and of being close to practical application in academic science and science-based industry.

Some current or recent projects include (1) elucidating reaction mechanisms in chemistry; (2) detecting subtle spatio-temporal patterns in biological imaging; (3) analyzing kinship terminologies in anthropological linguistics; (4) inferring particle models in high-energy physics. Also, we have recently developed very general methods for typological reasoning and are currently applying them to diverse fields.

Our main working hypothesis is that there are strongly generic elements present in scientific reasoning across the disciplines. This is obvious for highly mathematical tasks, but is less evident for the qualitative and symbolic inference that underly model building, pattern detection, and others.

My research area is Artificial Intelligence (AI). My current main research interest is the integration of machine learning with other areas of AI, in particular with problem solving/planning and with machine vision.

I have been working for several years in the Prodigy research project (see also Carbonell). Prodigy is a testbed for research in problem solving, planning and learning. I have studied different methods to learn control knowledge to improve the performance of a domain-independent problem solver. I developed learning algorithms for the integration of analogical/case-based reasoning and inductive explanation-based learning with general-purpose planning. I view the strategy-level learning process as the automation of the complete cycle of efficiently constructing, storing, retrieving, and flexibly reusing problem solving experience.

Towards this goal of improving planning performance from experience, we recently showed empirical evidence that there is no universally best domain-independent problem solving strategy. Therefore, I am currently interested in investigating new learning algorithms that integrate analytical, inductive, and experimental techniques to learn the correspondence between particular domain characteristics and specific search heuristics for planning effectively in complex domains.

My long term research goal is to bring AI systems and algorithms to a level that makes them applicable to real-world problems. To reach this goal, I have been expanding my work towards the integration of planning, execution, and learning in real robotics and information- processing agents. I am interested in combining multiple collaborative and adversarial reasoning agents in dynamic changing environments.

Furthermore, I have been investigating strategies in which the fields of perception, such as machine vision, and machine learning are combined to address jointly high-level and low-level real-world reasoning tasks. I aim at the development of autonomous agents capable of perceiving their surroundings through sensors, and improving their perception and problem solving ability through experience. I have recently started a new project for the integration of machine vision and machine learning. The goal of this project is to develop a new architecture where learning provides a flexible framework for the efficient recognition of everyday objects in in-door and out-door scenes. The architecture is currently based on a technique for learning object recognition algorithms by genetic programming where the image signals are used directly as a training and testing input. There is no built-in commitment to the manner in which the algorithms examine the images and the learning system evolves the algorithms to increase their decision-making fitness. The architecture has shown promising results in a challenging object recognition problem.

My research interests are in operating systems, networking, computer architecture and information systems. My emphasis has been in projects which cross multiple technologies, which led to my current large project which integrates several CS disciplines, from AI to systems.

The Informedia Digital Video Library.
Vast digital libraries of information will soon be available on the nation's Information Superhighway as a result of emerging technologies for multimedia data processing. The Informedia project is developing new technologies for data storage, search, and retrieval of video and audio content and embedding them in a distributed library system for use in education, training, sports and entertainment. The system uses intelligent, automatic mechanisms that provide full-content search and retrieval from an extremely large (scaling to several thousand hours) online digital video library. We are developing tools that can automatically populate the library and support access via desktop computers on local, metropolitan and wide area networks. Our approach uses combined speech, language and image understanding technology to transcribe, segment and index the linear video. These same tools will be applied to accomplish intelligent search and selective retrieval. Innovations include rapid retrieval of "video paragraphs" which satisfy an arbitrary subject query and "video skimming", which enables an accelerated viewing of the key video and audio sequences without the perceptual disturbance of simply speeding up the frame rate and audio.

The research involves the application of diverse technologies and disciplines to a single focused application. The system builds on existing technologies and extends with focused research:

• Speech understanding for automatically derived transcripts and spoken queries
• Image understanding for video "paragraphing" (segmentation) and similarity matching
• Natural language for processing transcripts and queries
• User interfaces for video display, manipulation and reuse
• Network authentication and billing for controlled access
• Data architectures for network retrieval-on-demand
• User studies for validation and assessment

My research interests center around the interpretation and integration of speech, language and other human communication signals in the design of human-computer and human-human communication systems. Two particularly challenging examples of these interests are the JANUS project, a speech-to-speech translation system, that provides translation of spoken language between English, German, Spanish, Japanese, Korean (e.g., a translating telephone). Another, the INTERACT project, attempts to design multimodal interfaces, that incorporate not only speech, but also other communication modalities, such as gesture, lipreading, handwritten character recognition, face- and eye-tracking, in order to derive a robust understanding of user intent.

The JANUS project has provided one of the earliest demonstrations showing that speech-to-speech translation is possible. I am now working on extending the system's toward high quality translation of unlimited spontaneously spoken and ins eom cases conversational human speech. This involves new inroads in robust understanding of spoken language, improved speech recognition methods, ways to automatically learn language as well as interactive and/or mobile ways of deploying such a system to meet natural multi-lingual communication needs. We are also extending JANUS to accept and produce additional languages flexibly.

The INTERACT project is aimed at enhancing human-computer communication to include other communication modalities known to be helpful in human communicative situations, such as observing where a person might be looking or focusing attention, decoding his/her handwriting, gesturing and pointing in conjunction with speech, observing lip movement to enhance recognition of speech, etc. Several real-life human-computer interaction applications are explored to see how these modalities can be usefully captured to make them a natural and reliable part of any human-computer or communication interface. In an effort to achieving these practical goals, computer systems must be able to learn and adapt to a changing environment and growing demands of a user. I am interested in various machine learning and modeling strategies to develop learning and adaptation. I am interested in CONNECTIONIST and STATISTICAL LEARNING and ADAPTATION strategies, particularly as applied to speech, language, visual and interactive signal processing. I am collaborating with other faculty to develop and enhance learning algorithms, that have the required properties for deployment in the real world.

My primary research areas are understanding spontaneous speech, language modelling for spoken language understanding, and binaural phenomena.

Understanding speech is different from understanding text in that the words are not given. The system must decode the words from the speech signal using acoustic evidence and a language model. The language model that it uses may include many different types of information including syntactic and semantic relationships, probabilities of sequences, and expectations based on dialog and prosodics. The task is particularly difficult when the input is ill-formed. Users may use words not in the systems's lexicon or constructions not legal in its grammar. Some words in the input may not have been correctly recognized. Users make noises that don't correspond to words (filled pauses, coughs, etc). This type of input arises when users speak in a spontaneous manner rather than reading text. The process must be robust enough to allow portions of the speech to be unrecognized and still correctly process the rest.

My research in the near future will be directed at ways of handling spontaneous input in a speech understanding system. Recognition failures and other ill-formed input don't necessarily have to result in communication failures. A speech understanding system must detect and respond to ill-formed input. In many instances, the system may proceed without a problem. At worst, a meaningful error response must be given to the user.

I am also interested in deriving language models from examples. Given a domain knowledge base, some general knowledge of English language grammar and a corpus of example sentences, how can one derive a language model specific to the domain?

My general research interests lie in distributed systems, programming languages, and software engineering. I especially enjoy integrating approaches from these different areas and applying results from more theoretical work on languages to practical problems found in real systems. A long-term goal that drives my research is to provide, where appropriate, as rigorous as possible a foundation to the design and implementation of software.

My specific interest is the application of formal methods to reason about complex software systems. Formal methods play an important role in all aspects of software development and can be used to state a system's properties precisely and unambiguously. To give a flavor of the kinds of problems I like to tackle, here are some case studies in the application of formal methods that I have recently done with fellow students and colleagues:

• authentication and electronic cash protocols
• cache coherence in distributed file systems
• error recovery for families of RAID architectures
• dynamic sets used for search through the Web
• mobile internetworking protocols

My past research projects include:

1. Larch, a family of specification languages noted for its two-tiered approach to specifying program modules;
2. Miro, a visual specification language for specifying file system security constraints;
3. Avalon, extensions to C++ and CommonLisp to support distributed transactions;
4. Venari, extensions to Standard ML to support concurrent multi-threaded transactions; and signature and specification matching of software components.
5. TinkerTeach, software infrastructure for electronic delivery of courseware.

The primary goal of my research is to create new interactive computer modeling media based on real-time physical simulation and control. The basic idea is to permit users to build models by manipulating virtual materials that move and deform in response to applied forces. Imagine, for example, building a mechanism out of simple parts that snap together like tinkertoys, or developing a model for a complex shape by forming, cutting, and joining flexible sheets.

Our core effort is aimed at developing the mathematical and computational foundations that are required to support interactive simulation. In this area, we are concerned with the problem of quick, accurate, and robust calculation of objects' differential motion subject to constraints. The constraints might represent mechanical connections and interactions, or simply reflect the model builder's desires. Calculating the constrained motion involves the solution of large but sparse systems of linear equations. Obtaining solutions interactively is a difficult task because the structure of the sparse matrix changes each time the user adds or removes an object or constraint. We have developed algorithms that operate on model graphs to efficiently extract these matrices on the fly. Our algorithms are embedded in a modeling toolkit which forms the substrate for many of our applications.

As we develop these basic capabilities, we are also pursuing several of the many potential applications in science, design, graphics, and animation.

One exciting application is in the area of free-form surface design. Most current modeling systems require the user to form surfaces by manipulating a fixed mesh of control points, each of which exerts local influence on the surface's shape. This can be an awkward mechanism, often requiring the user to precisely reposition a great many control points to effect conceptually simple changes to the surface. Our alternative is based on active surface models that continually try to maximize their smoothness subject to the constraints imposed on them. The user may grab or pin the surface at arbitrary points or along arbitrary curves, using the points and curves as customized shape controls. Complex models are formed by cutting and joining multiple surface sheets.

Another application area involves the design and analysis of mechanisms: in conceptual design, simple pieces can be literally snapped together to form constrained assemblies, which the user may then manipulate interactively. We are also addressing more specialized design applications, such as the analysis and adjustment of tolerances.

Computer animation raises special problems of motion control. Standard keyframe methods depend entirely on the animator's skill and perseverance to produce pleasing animation. Our methods make it possible to control motion much more directly and economically. For instance, a character's hand may be accurately dragged along a specified path as if it were sliding on a wire, while the direction of gaze is constrained to follow a moving target, and while the feet are kept firmly planted on the ground. This sort of coordinated action is surprisingly difficult to achieve using traditional methods. Motion control of the virtual camera is an important special case. Here, we have developed "through-the-lens" control techniques that allow camera motions to be specified by what the camera sees, for instance requiring that certain objects be kept in view, or held at particular positions in the image.

Finally, we are applying the same basic machinery to biological modeling and data analysis, aimed at understanding intracellular mechanics. To analyze the motion and deformation of structures visualized by fluorescent light microscopy, we create active models whose behavior is coupled, through the data to that of the actual structures.

My research interests span several areas of information access, including text categorization, retrieval, clustering, summarization, multimedia and translingual information access, and intelligent search in digital libraries and the Internet environment. My work includes the development of a novel learning method ("the Linear Least Squares Fit Mapping") using multi-variate regression in high dimensional source/target spaces, evaluation and comparison of various statistical learning methods in solving real-world problems, and the development of several state-of-the-art classification systems that scale up to very large applications such as Japanese patent classification (using a hierarchy of 60,000 categories), patient record coding (using a taxonomy of 30,000 disease classes), bibliographical database indexing and retrieval (using 18,000 MEDLINE subject categories), news story topic spotting, etc. The production versions of these systems have been used for computer-aided indexing of practical databases, such as the Mayo Clinic patient records archive.

My research interests lie in computer networks, Internet, multimedia systems, resource management, and performance analysis. My work involves both designing practical algorithms with sound theoretical foundations and building prototype systems in real life environments. In the area of algorithm design, I study scheduling, traffic modeling and characterization, admission control, routing, and multicast algorithms. In the area of systems research, I build Internet and ATM protocols, experimental network testbeds, and distributed real-time multimedia applications. I participated in the design and implementation of several high speed network testbeds including SequoiaNet and Xunet, and was one of the principle designers and implementors of the U.C. Berkeley Tenet Real-Time Protocol Suite.

My current research focus is on designing resource models and resource management algorithms for next generation service-oriented application- aware networks. As the network becomes more ubiquitous and high performance, we see two trends. On one hand, internetwork layer protocols such as IP will be relatively stable and evolve slowly. On the other hand, there will be a growing need for rapidly developing and deploying sophisticated applications and network services (e.g., Pointcast and distributed simulation). To bridge the gap, we envision the emergence of a service-oriented network where value-added distributed services such as reliable multicast, caching, video/audio transcoding and mixing, and translation of different languages are provided to applications on top of a bitway network such as the Internet. We propose a new network abstraction based on a hierarchy of application or service virtual (logical) networks that consist of distributed virtual resources such as communication links, CPUs, and storage. Each virtual network is built on top of one or multiple other virtual networks, utilizing the services provided by the underlying networks, and provides added value. Top level virtual networks are application virtual meshes while the lowest level virtual network is the physical bitway that provides point-to-point or a primitive form of multiple point data movement services.

Resource management in such a hierarchical service-oriented Internet presents several important challenges that are not present in the Internet today. First, each virtual network should provide not only added value in terms of functionalities, but also QoS as it were controlling physical resources directly. While the current Internet integrated service model supports Quality of Service (QoS) mainly on the basis of individual traffic streams, sophisticated services and applications that consist of many simultaneously active traffic streams will want to have application/service specific resource management policies for their virtual resources. Since there is a dynamic hierarchy of virtual networks that share the same physical network, it is important that resources are managed in a hierarchical and dynamic fashion so that resource management policies for all virtual networks can be accommodated simultaneously. Second, there are multiple types of resources to be managed. In addition to link bandwidth, there are also shared CPU, memory, and storage resources that are needed to provide added value. Even though these resources have different characteristics, we would like to have a unified framework for accounting and managing these resources. Third, effective resource management requires application end nodes, service nodes, and network switch nodes to negotiate and coordinate. While negotiation and coordination have the potential of making the system more adaptive and resource utilization more efficient, they may also introduce overhead and make the system less robust and secure. It is important to devise protocols and algorithms that achieve robust, efficient, and secure negotiations and coordinations.

I am currently attacking the above problems in the context of several projects. In the Darwin project (with Allan Fisher and Peter Steenkiste), we have developed and implemented two scheduling algorithms (Hierarchical Packet Fair Queueing and Hierarchical Fair Service Curve) that provide the basic mechanism for hierarchical application/service specific resource management inside the network. We are evaluating these algorithms in several wide-area high speed network testbeds (Dartnet/CAIRN/vBNS). In the resource-centric kernel and network project (with Raj Rajkumar), we are investigating a unified framework for managing CPU, link, and memory resources. In the the NASD project (with Garth Gibson), we are building a distributed video server that can efficiently support sophisticated multimedia applications such as Informedia by taking advantages of the capabilities provided by new network services.

Abstraction (cf. Type Theory): Garlan, Shaw, Wing
Adaptive systems: Goldstein, Maxion
Algol-like languages: Reynolds
Algorithms: Blelloch, Blum, Bryant, Furst, Lafferty, G. Miller, Rudich, Sleator, Tygar
Algorithms, approximation: Blum
Algorithms, distributed: Johnson, Rudich, Tygar
Algorithms, graph: Blum, G. Miller
Algorithms, learning: Blum, Carbonell, Fahlman, Lafferty, McClelland
Algorithms, on-line: Blum
Algorithms, parallel: Blelloch, Fisher, Furst, Maggs, G. Miller, Tygar
Algorithms, robot: Erdmann
Analogical reasoning: Carbonell, Mitchell, Veloso
Animation:: Heckbert
Application-specific computing systems: Garlan
ATM networks: Fisher, Steenkiste, Zhang
Auditory modeling: Stern, Ward
Automated theorem proving: Clarke, Pfenning, Scott, Wing
Automatic compiler generation: P. Lee
Automatic grammar generation: Lafferty, Waibel, Ward
Automatic parallelization: Goldstein, Gross, Subhlok
Automatic programming: See Program Synthesis.
Automatic Presentation Design: Roth
Automatic speech understanding: Rosenfeld, Waibel, Ward
Autonomous mobile robots: Kanade, Simmons
Autonomous land vehicles: Simmons
Autonomous spacecraft: Simmons
Autonomous systems: Kanade

Biology, computational: Valdes-Perez

Causal reasoning: Carbonell, Maxion
Character recognition: Waibel
Code generation and optimization: Gross
Cognitive architecture: Carbonell, John, Lehman
Cognitive modelling: Carbonell, John, Lehman, Maxion, Plaut
Cognitive science: Carbonell, John, Koedinger, Lehman, McClelland, Maxion, Plaut
Combinatorics: Furst, G. Miller, Rudich, Sleator
Compilers: Blelloch, Fisher, Gibson, Goldstein, Gross, Harper, P. Lee, Steenkiste, Subhlok
Complexity theory: Furst, Rudich
Computation theory: Brookes, Clarke, Furst, Lafferty, G. Miller, Rudich, Scott
Computational finance: Rosenfeld
Computational group theory: Lafferty
Computational linguistics: Carbonell, Hauptmann, Lafferty, Lehman, McClelland, Plaut, Rosenfeld, Rudnicky, Scott, Waibel, Ward
Computational science: Valdes-Perez
Computer-aided design: Bryant, Clarke, Garlan, John, Siewiorek
Computer-aided instruction: Christel, Pfenning
Computer architecture: Blelloch, Fisher, Ganger, Gibson, Goldstein, Gross, Siewiorek, Steenkiste, Wactlar
Concept formation: Carbonell, Maxion, Mitchell
Concurrency, semantics of: Brookes, Clarke, Wing
Concurrent systems: Wing
Connectionist networks: See Neural nets.
Constraint logic programming: Pfenning
Constructive mathematics: Harper, Pfenning, Scott
Control theory: Moore
Cooperative computation: Touretzky
Cooperating robots: Erdmann
Cryptanalysis: Tygar, Rudich
Cryptography: Furst, Rudich, Tygar

Data mining: Carbonell, Mitchell, Moore
Data structures: Sleator
Databases (cf. Information retrieval): Gibson, Satyanarayanan
Data types: See Abstraction, see Type Theory.
Debugging: Gross, Johnson
Dependability: See Reliability.
Design automation: See Computer-aided design.
Diagnosis and diagnostic reasoning: Maxion
Dialog: Rudnicky, Ward
Digital cartography: Cochran, McKeown
Digital video: Christel, Wactlar
Discourse modelling: Lehman
Discovery, scientific: Maxion, Mitchell, Simon, Valdes-Perez
Distributed computing: Gibson, Goldstein, Johnson, O'Hallaron, Steenkiste
Distributed file systems: Ganger, Gibson, Satyanarayanan
Distributed systems: Clarke, Dannenberg, Ganger, Gibson, Johnson, Maxion, O'Hallaron, Satyanarayanan, Steenkiste, Tygar, Wing

Education, computer science: Brookes, Pfenning, Shaw
Educational technology: Christel, Dannenberg, Wing
Electronic commerce and negotiation: Tygar
Emergent computation: Maxion
Experimentation: Satyanarayanan, Carbonell, Gibson, Johnson, Maxion, Mitchell,
Expert systems: See Knowledge-based systems.
Explanation: Mitchell, Roth
Eye-tracking: Waibel

Face tracking: Waibel
Fault tolerance: See Reliability.
File systems: Ganger.
File usage properties: Ganger, Gibson, Satyanarayanan
Formal methods: Garlan, Wing
Formal methods in AI: Garlan, Mitchell, Touretzky
Forsythe: Reynolds
Foundations of mathematics: Harper, Scott
Functional programming: Blelloch, Harper, P. Lee, Pfenning, Reynolds, Scott

Game-playing, computer: Rudich, Sleator
Game theory: Moore
Geometric modeling: Heckbert
Gesture recognition: Waibel
Graceful Degredation: McClelland
Graphics: Cochran, Heckbert, McKeown, Pausch, Roth, Witkin
Gwydion: Fahlman

Hand-eye systems: Mitchell
Heuristic Search: Moore
Higher-order logic: See Type theory.
Human-computer interaction: Christel, Cochran, Dannenberg, John, Koedinger, Maxion, Olsen, Pausch, Roth, Rudnicky, Shaw, Waibel, Ward
Human factors: Hauptmann, John, Maxion, Pausch, Rudnicky, Waibel
Human language technology: Rosenfeld, Waibel
Hypercode: Fahlman

Image processing: Heckbert
Image understanding: See Vision.
Industrial computing: Rajkumar
Inferential programming: Scott
Information retrieval: Carbonell, Mitchell, Scott, Wing, Yang
Information systems: Wactlar
Input/Output: Ganger, Gibson
Integrated-services networks: Zhang
Intelligent architectures: Carbonell, John, Lehman, Mitchell, Simmons
Intelligent interfaces: Roth
Intelligent tutoring systems: Dannenberg
Interactive graphic programming: Pausch
Interfaces, Human-computer: Carbonell, Christel, Dannenberg, John, Maxion, Pausch, Reddy, Rudnicky, Scott, Shaw, Waibel, Ward
Internet: Ganger, Johnson, Zhang
Interprocess communication: Blelloch, Goldstein, Gross, Johnson

Knowledge acquisition: Carbonell, Cochran, Lehman, Maxion, McKeown, Mitchell
Knowledge-based systems: Carbonell, John, Lehman, McKeown, Mitchell, Valdes-Perez
Knowledge representation: Carbonell, Fahlman, Furst, Mitchell, Scott, Touretzky

Lambda calculus: Harper, Pfenning, Scott
Language acquisition: Lehman, Waibel, Ward
Language design: Fahlman, Shaw
Language implementation: Blelloch, Fahlman, Harper, P. Lee
Language modelling: Carbonell, Lafferty, Rosenfeld
Learning theory: Blum, Lafferty, Rudich
Library: Christel, Wactlar
Linear algebra, computational: G. Miller
Linguistics: See Computational Linguistics.
Lipreading: Waibel
Lisp: Clarke, Fahlman, Touretzky
Logic: Brookes, Harper, Pfenning, Scott
Logical frameworks: Harper, Pfenning
Logics of programs: Brookes, Clarke, Harper, Pfenning, Scott

Machine learning: Carbonell, Fahlman, Lafferty, Lehman, Maxion, Mitchell, Moore, Reddy, Rosenfeld, Simon, Valdes-Perez, Waibel, Ward
Machine translation: Carbonell, Hauptmann, Lafferty, Rosenfeld, Waibel
Manipulation: Erdmann, Mason, Mitchell
Manufacturing: Moore
Markov models: Simmons
Mathematics of Computation: Furst, G. Miller, Rudich
Measurement and evaluation: Gibson, Johnson, Maxion, Satyanarayanan
Medical robotics/computer-assisted surgery: Kanade
Memory architecture: Gibson
Mobile computing: Johnson, Pausch, Siewiorek
Mobile networking: Johnson
Mobile robotics: Mitchell, Moore, Pomerleau, Simmons
Model checking: Wing
Monitoring and error recovery: Simmons
Motion planning: Erdmann, Moore
Multicomputers: Gibson, Goldstein
Multilingual Spoken Language Systems: Waibel
Multimedia: Christel, Dannenberg, Fisher, Gibson, Kanade, Rajkumar, Wactlar, Zhang
Multimodal interfaces: Pausch, Rudnicky, Waibel
Multiprocessors: Fisher, Garlan, Goldstein
Music, computer: Dannenberg, Scott

Natural language generation: Lehman
Natural language processing: See Computational Linguistics.
Network-aware applications: Ganger, Johnson, Steenkiste, Subhlok, Zhang
Network protocols: Ganger, Johnson, Satyanarayanan, Steenkiste, Zhang
Networking: Fisher, Ganger, Gibson, Johnson, Maxion, Steenkiste, Wactlar, Zhang
Neural Networks: Blum, Fahlman, Furst, McClelland, Plaut, Pomerleau, Touretzky, Waibel, Ward
Neuroscience: T. Lee, Touretzky
Numerical methods: G. Miller

Object-oriented programming: Wing
Operating systems: Ganger, Gibson, Johnson, Rajkumar, Tygar, Wactlar

Parallel AI: Touretzky
Parallel applications: Gibson, Goldstein
Parallel architectures: Blelloch, Fisher, Gibson, Goldstein, Gross, G. Miller
Parallel computing: O'Hallaron
Parallel file systems: Gibson
Parallel models of computation: Blelloch, G. Miller
Parallel processing: Blelloch, Brookes, Bryant, Clarke, Fisher, Gibson, McClelland, Steenkiste, Touretzky, Tygar
Parallel programming: Blelloch, Fisher, Gross, O'Hallaron, Steenkiste, Subhlok
Parallel program generators: Subhlok
Parallel systems: O'Hallaron, Tygar
Parallelizing compilers: Goldstein, O'Hallaron, Subhlok
Parsing, natural language: Carbonell, Lafferty, Sleator, Ward
Pattern Recognition: Lafferty, Waibel
Perception, auditory: Stern, Ward
Performance evaluation: Ganger, Gibson, Johnson, Maxion, Satyanarayanan, Zhang
Photogrammetry: McGlone
Planning: Blum, Carbonell, Erdmann, Mason, Mitchell, Simmons, Veloso
Polymorphism: Harper, Pfenning, Reynolds
Problem-solving: Carbonell, Erdmann, Mitchell
Probabilistic planning: Simmons
Process control: Maxion
Program analysis: P. Lee
Program manipulation tools: Scherlis
Program optimization: Goldstein, Subhlok
Program synthesis: Erdmann, Mason
Program transformation: Blelloch, Brookes, Scherlis, Scott
Program visualization: Garlan, Tygar
Programming environments: Dannenberg, Fahlman, Garlan, Pausch, Scherlis, Scott, Shaw
Programming languages: Blelloch, Brookes, Clarke, Dannenberg, Fahlman, Harper, P. Lee, Pfenning, Reynolds, Scherlis, Scott, Shaw, Wing
Programming methodology: Brookes, Clarke, Garlan, Pausch, Pfenning, Scherlis, Scott, Shaw, Wing
Proof theory: Harper, Pfenning, Scott
Protocols: Gibson, Johnson, Rudich, Satyanarayanan, Tygar, Zhang
Protocol Analysis: John, Maxion
Psychology: John, Maxion, Rudnicky

QoS Management: Rajkumar

Randomization: Erdmann, Rudich, Tygar
Reading Theory: Roth
Real-time networks: Zhang
Real-time systems: Dannenberg, Rajkumar
Reasoning, Inheritance: Touretzky
Reasoning, Non-monotonic: Touretzky
Reconfigurable Computing: Goldstein
Recovery: Johnson
Reflection: Mitchell
Reinforcement learning: Moore
Reliability: Ganger, Gibson, Goldstein, Johnson, Maxion, Satyanarayanan, Siewiorek, Tygar, Wing
Remote execution: Tygar, Wing
Remote procedure call: Johnson
Remote sensing: Cochran, McKeown
Rendering: Heckbert
Requirements analysis: Maxion
Resource management: Zhang
Robot programming: Erdmann, Mason
Robotics: Erdmann, Kanade, Mason, Mitchell
Routine design: Shaw

Scheduling: Moore
Scientific discovery: Maxion, Mitchell, Simon, Valdes-Perez
Scientific computing: Heckbert, O'Hallaron, Subhlok
Search: Valdes-Perez
Search, Beam: Ward
Secure remote execution: Tygar
Security: Gibson, Johnson, Satyanarayanan, Tygar, Wing
Semantic networks: Fahlman, Touretzky
Semantics-based program analysis: P. Lee
Semantics-based compiler generation: P. Lee
Semantics-based program manipulation: Scherlis
Semantics of natural languages: Lehman, Scott
Semantics of programming languages: Brookes, Clarke, Harper, P. Lee, Pfenning, Reynolds, Scott, Wing
Semiconductor fabrication: Maxion
Sensing, action, prediction: Erdmann
Signal processing: Dannenberg, Stern, Ward
Simulation: Bryant, Gibson, Johnson
Software architectures: Garlan, Scherlis, Shaw
Software construction: Gross
Software design methods: Garlan, Shaw
Software engineering: Fahlman, Garlan, Scherlis, Shaw, Wing
Spatial databases: McKeown
Spatial reasoning and representation: Cochran, Erdmann, McKeown, Mason
Specialized architectures: Fisher, Goldstein
Special-purpose systems: Fisher, Goldstein
Specification: Brookes, Clarke, Garlan, Harper, P. Lee, Pfenning, Reynolds, Scott, Shaw, Tygar, Wing
Speech Based Instructional Software: Roth
Speech recognition: Rosenfeld, Stern, Waibel
Speech synthesis: Hauptmann
Speech translation: Waibel
Speech understanding: Hauptmann, Reddy, Rudnicky, Stern, Waibel, Ward
Statistics: Lafferty, Moore, Rosenfeld
Stochastic Modeling: Gibson, Lafferty, Rosenfeld, Waibel, Ward
Storage: Ganger, Gibson
Supercomputers: Blelloch, Fisher, Gibson, Goldstein, Reddy, Subhlok
Symbolic computation: Bryant, Scott

Tactile sensing: Mason
Task representation: Moore
Task-level control: Simmons
Telecommunication: Zhang
Text, electronic: Scott
Text processing: Carbonell, Rosenfeld
Theory formation: Mitchell, Valdes-Perez
Transaction processing: Wing
Typesetting: Scott
Type theory: Harper, P. Lee, Pfenning, Reynolds, Scott

Usability evaluation: John, Maxion, Pausch
User models: John, Maxion

Verification: Brookes, Bryant, Clarke, Harper, Reynolds, Scott, Wing
Virtual(ized) reality: Kanade, Pausch
Vision: Cochran, Kanade, McGlone, McKeown, Pomerleau
Vision, 3D: Kanade
Visual programming: Garlan, Tygar
Visualization: Christel, O'Hallaron, Pausch, Roth
VLSI: Blelloch, Brookes, Bryant, Clarke, Fisher, Goldstein
VLSI-based sensors: Kanade

Wireless networking: Johnson

cmcc: Gross
Coda File System: Satyanarayanan
Composable Systems: Garlan, Shaw, Wing
Computational neuroscience: T. Lee, McClelland, Plaut, Touretzky
Computer Music: Dannenberg
Connectionist Research Group: Fahlman, McClelland, Plaut, Touretzky
COSMOS (COmpiled Simulator for MOS circuits): Bryant
Credit Net: Steenkiste
Cryptographic Stamps: Tygar

Darwin: Fisher, Steenkiste, Zhang
DSSC (Data Storage Systems Center): Ganger, Gibson
DEMETER: Siewiorek
Design for Manufacturing: Siewiorek
DIPLOMAT: Carbonell, Frederking, Rudnicky
Distributed Sensor Networks (DSN): Reddy
Dyad: Tygar
Dynamic Source Routing: Johnson

Electronic Franking: Tygar
Elf: Pfenning
EMC (Extended Model Checker): Clarke
ENVISAGE (Graphical Data Manipulation): Roth
Exokernel: Ganger
Experience on Demand": Christel, Hauptmann, Kanade, Wactlar

Fault Tolerance: Maxion
FISPE Project: Koedinger
Fox: Harper, P. Lee, Pfenning
Forsythe: Reynolds
Fx: Gross, O'Hallaron, Subhlok

GOMS: John
Gwydion: Fahlman

Harbinger: Maxion
HERO Robot: Mitchell
High Performance Computing Graphics: Heckbert
Image Understanding (IU): Kanade
Informedia: Christel, Hauptmann, Kanade, Wactlar
INTERACT: Waibel
Interactive Systems Lab: Waibel
ITOSS (Integrated Toolkit for Operating System Security): Tygar

JANUS: Waibel

KANT Knowledge-Based Automated Natural Language Translation: Carbonell
Larch: Wing
Learning Robot: Mason, Mitchell
LISTEN (Speech Recognition of Reading): Roth

MAPS (Digital Mapping Lab): Cochran, McGlone, McKeown
McDonnell Project: Koedinger
MECHEM: Valdes-Perez
Medical Robotics: Kanade
Mercator (coordinated mapping and planning): Simmons
Mercury (Electronic Library Project): Morris, Scott
MESS: P. Lee
MICON: Siewiorek
Miro: Tygar, Wing
Mobile computing: Johnson, Satyanarayanan
Mobile IP: Johnson
Monarch: Johnson
Multi-Modal Human-Computer Interface: Waibel

NASD (Network-Attached Secure Disks): Gibson, Tygar, Nagle, Zhang
NAVLAB: Pomerleau
Nectar: Steenkiste
NetBill: Tygar
Network Diagnosis: Maxion
New Millennium (autonomous spacecraft): Simmons
Nomad (Lunar Rover): Simmons
NPen++: Waibel

Odyssey: Satyanarayanan
OZ: Hauptmann

PACT (Pittsburgh Area Cognitive Tutoring) Center: Koedinger
Parallel Data Laboratory: Gibson
PARTHENON: Clarke
PENCHANT: Valdes-Perez
PHOENIX: Ward
POP (Principles of Programming): Harper, P. Lee, Pfenning, Reynolds,
Scott, Wing PRODIGY: Carbonell, Veloso
Quake: O'Hallaron
Quality of Service (QoS): Zhang

RAIDframe (Rapid Prototyping for RAID): Gibson
REMULAC: O'Hallaron, Subhlok
RT-Mach: Rajkumar

SAGE (Automatic Presentation: Roth
Security Library: Tygar
Secure Coprocessors: Tygar
SLS Spoken Language Systems: Ward
SOAR: John, Lehman
Speech Understanding: Hauptmann, Reddy, Rosenfeld, Rudnicky, Stern, Waibel, Ward
SPFS (Scotch Parallel File System): Gibson
StrongBox: Tygar

TCA (Task Control Architecture): Mitchell, Simmons
TDL (Task Description Language): Simmons
THEO: Mitchell
3D (Visualization and Interaction): Roth
TIP (Informed Prefetching File System): Gibson
TinkerTeach: Garlan, Shaw, Wing
TDT (Topic Detection and Tracking): Carbonell, Lafferty, Yang
TPS: Pfenning

UniCon: Shaw
Universal Library project: Carbonell, Reddy, Shamos, Thibadeau

Venari: Wing
Virtual World Simulation: McKeown
Virtualized Reality: Kanade
Vitruvius: Shaw

Word Learning: Ward

XAVIER (Office-delivery robot): Simmons