• Computer Science

  • FileName: CS.pdf [read-online]
    • Abstract: Computer ScienceM. Heath, Interim Head Applications (NCSA), Beckman Institute for AdvancedM. Harandi, Associate Head Science and Technology, The Illinois Trust Institute (ITI),

Download the ebook

Computer Science
M. Heath, Interim Head Applications (NCSA), Beckman Institute for Advanced
M. Harandi, Associate Head Science and Technology, The Illinois Trust Institute (ITI),
1332 Thomas M. Siebel Center for Computer Science the Institute for Genomic Biology (IGB), and the
201 N. Goodwin Ave. Coordinated Science Laboratory (CSL).
MC-258 M. Snir was department head during the reporting period.
Urbana, IL 61801-2302
217-333-3426 Faculty and Their Interests
Sarita Adve
For more than fifty years, the Department of Computer
Computer architecture, low-power design, adaptive
Science at the University of Illinois has quietly led a
systems, real-time and network processing, performance
revolution that has redefined the meaning of computing.
evaluation methods, parallel computing
Our students and faculty have designed and built the
world’s fastest computers, created the user interfaces that
Vikram Adve
popularized the World Wide Web and helped make
Compilers, software reliability, performance analysis,
distributed collaboration possible, invented the
computer architecture
compilation techniques for automatic programming
parallelization, co-founded the field of computer
Gul A. Agha
arithmetic, discovered new techniques for numerical
Developing new abstractions for building open distributed
solution of stiff ordinary differential equations, and carried
systems and reasoning about their behavior, parallelism,
out seminal work in parallelizing compilers.
coordination, real-time behavior
The department offers an array of powerful computers
and software for instruction, as well as research Eyal Amir
laboratories maintained by individual faculty. All systems Automated reasoning and machine learning
are connected to a high-speed network with multiple
wireless networks also available. The department also Brian P. Bailey
provides computer clusters, printers, file services, and User interface tools that better support early design tasks,
other technology services for all of its users. In early 2004, systems and environments that help users maintain
the department relocated to the Thomas M. Siebel Center information awareness, tools for multimedia authoring and
for Computer Science, which serves as a living laboratory design, interfaces that foster social interaction, human–
for exploring and evaluating 21st century computing computer interaction
Current research areas include the following: Geneva G. Belford, Emeritus
algorithms and theory; artificial intelligence in the areas of Databases and information systems, distributed systems
machine learning, vision, and robotics; computer
architecture and compilers; databases and information Stephen Bond
systems; graphics and visualization; human–computer Numerical analysis and scientific computing, with
interfaces and social computing; networking; operating applications in statistical mechanics, and biochemistry;
systems and security; parallel processing; programming understanding methods that bridge the temporal and spatial
languages, formal systems, and software engineering; real- scales in multiscale biomolecular modeling using
time and embedded systems; bioinformatics; and scientific techniques from geometric integration and adaptive finite
computing. element methods
The department is also home to the Center for
Simulation of Advanced Rockets (CSAR) and the Center Marco Caccamo
for Advanced Research in Information Security (CARIS). Real-time operating systems, real-time scheduling and
It has many collaborative ties with units throughout resource management, wireless sensor networks, quality of
campus, including the National Center for Supercomputing service control in next-generation digital infrastructures
Roy H. Campbell Indranil Gupta
Security, distributed operating systems, ubiquitous Distributed systems, distributed protocols, probabilistic
computing protocols, design methodologies, sensor networks
Kevin C.-C. Chang Jiawei Han
Databases, Internet information access, and digital Database systems, data mining, data warehousing, stream
libraries, with focuses on information integration of data mining, web mining, spatiotemporal data mining,
heterogeneous sources, Internet query processing, web biodata mining
databases, and ranked top-k query processing
Mehdi T. Harandi
Chandra Chekuri Artificial intelligence, information systems, HCI, software
Design and analysis of algorithms, combinatorial engineering
optimization, approximation algorithms, scheduling,
graphs, networks Sariel Har-Peled
Algorithms, data structures, computational geometry,
Gerald DeJong clustering, learning, computer graphics
Artificial intelligence
Luddy Harrison
Eric deSturler System architecture
Iterative methods, eigenvalue problems, large-scale
optimization John C. Hart
Computer graphics, computational topology
AnHai Doan
Databases, data integration and sharing, data mining, Michael T. Heath
information discovery on the Web, efficient use and Scientific computing, parallel computing
maintenance of meta-data, schema matching, machine
learning Jennifer C. J. Hou
Design, analysis and implementation of self-adjusting
Jeffrey G. Erickson protocols for wireless networks, enabling technology for
Algorithms, data structures, and lower bounds; large-scale network simulation and emulation, wireless-
computational and discrete geometry enabled cyber physical space for healthcare, design,
fundamental property analysis, evaluation of data-centric
Margaret Fleck wireless sensor networks
Automated reasoning and machine learning
Sheldon H. Jacobson
David Forsyth Operations research, discrete optimization, heuristic
Artificial intelligence, computer vision, machine learning design and analysis, applied probability, health care,
aviation security, homeland security
Michael Garland
Computer graphics, geometric modeling, human– Ralph E. Johnson
computer interaction, visualization Object-oriented design, design patterns, frameworks,
software architectures
Maria J. Garzaran
Compilers, software reliability, parallel computer Laxmikant V. Kale
architecture, thread-level speculation Numerical, parallel, and scientific computing, operating
Elsa Gunter
Formal systems Samuel N. Kamin
Programming languages, software components, functional
Carl A. Gunter programming applied to scientific computation,
Security, networks, software engineering, programming denotational semantics, program specification and
languages verification, domain-specific languages
Karrie Karahalios Jean A. Ponce
Human–computer interfaces Computer vision, robotics, computer graphics
Samuel T. King Manoj M. Prabhakaran
Security, operating systems, experimental software Cryptography, other topics in theoretical computer science
systems, virtual machines
Grigore Rosu
Robin Kravets Software and software related aspects; design, semantics,
Mobile computing and communication, location and implementation of programming and specification
management, power management, transport protocols, ad languages; automated software engineering and formal
hoc networks, personal area networks methods, especially "push-button'' techniques for
certification, monitoring, synthesis, and modularization;
Steven M. LaValle automated reasoning about computer systems, applications
Robotics, motion planning, computational geometry, of logics, theorem proving; algorithms, (co)algebra,
artificial intelligence, computational biology, computer category theory
vision, computer graphics, control theory
Dan Roth
Haiyun Luo Artificial intelligence, theoretical computing
Networking and distributed systems
Lui Sha
Darko Marinov Distributed real-time computing systems, dynamic real-
Software engineering, programming languages, software time architecture, Quality-of-Service (QoS) driven
testing resource management, security and fault tolerance in
networked embedded systems
Jose Meseguer
Formal executable specification and verification; software Saurabh Sinha
composition, reflection, and metaprogramming; object- Gene regulation, comparative genomics, sequence
oriented specification and software architecture; analysis, evolution
concurrent, distributed, and mobile computing; logical
frameworks and formal interoperability; logical and Marc Snir
semantic foundations Large-scale parallel and distributed systems, parallel
computer architecture, grid computing, parallel
Klara Nahrstedt programming
Quality-of-Service (QoS) management, integration of
guaranteed and best effort services for audio/video/DATA Josep Torrellas
traffic, QoS-aware resource management, QoS routing, Parallel and sequential computer architecture, processor-
multimedia security, soft real-time scheduling, memory integration, thread-level speculation, low power
middleware support for distributed multimedia design, reliability
Mehesh Viswanathan
Luke Olson Analysis and validation of software systems, including
Numerical partial differential equations (PDEs), numerical design of efficient algorithms, characterization of
linear algebra, high-performance computing computational limitations, development of formal models
for system specification, and implementation of software
David A. Padua tools for program analysis
Computer architecture and systems, parallel computing,
compilers Marianne S. Winslett
Databases, security, parallel computation
Madhusudan Parthasarathy
Software engineering, formal methods Yizhou Yu
Data-driven graphical methods, computer animation, mesh
Lenny Pitt editing, image and video processing
Artificial intelligence, theoretical computing
Chengxiang Zhai risking approaching cars, passing slow-moving vehicles,
Text processing and management, statistical natural and parking. The resulting car would compete in the
language processing, machine learning, bioinformatics DARPA Urban Challenge in November 2007. The
resulting technology could revolutionize the way we live,
Yuanyuan Zhou with potential for fewer traffic accidents, cheaper services
Operating systems, file and storage systems, architecture, (e.g. transportation of goods, street cleaning) and others.
distributed systems, parallel systems, system support for
Goal Achievement in Partially Known, Partially
Observable Domains
Craig Zilles E. Amir,* A. Chang
Computer architecture, dynamic optimization, compiler Defense Advanced Research Projects Agency (DARPA),
construction, simulation methodologies, computer science HR0011-05-1-0040
education We present a decision-making algorithm for agents that act
in partially observable domains that they do not know fully.
Algorithms and Theory Making intelligent choices in such domains is very difficult
because the effects of actions may not be known a priori
(partially known domain), and features may not always be
Approximation in Computational Geometry
visible (partially observable domain). Nonetheless, we
S. Har-Peled*
show that an efficient solution is achievable in STRIPS
University of Illinois
domains by using traditional planning methods. This
This research has concentrated on the development of solution interleaves planning and execution carefully.
approximation algorithms. These algorithms provide a Computing each plan takes time that is linear in the
close-to-optimal solution and tend to be simple and easy to planning time for the fully observable, fully known
implement. Research encompasses both theory and domain. The number of actions that it executes is bounded
implementation, with a focus on developing general by a polynomial in the length of the optimal plan in the
techniques that perform well in practice. The research also fully observable, fully known domain. Our theoretical
will explore applying the insights and techniques from results and preliminary experiments demonstrate the
computational geometry to other fields, such as databases, effectiveness of the algorithm.
data mining, graphics, and geographic information
Knowledge-Based Learning Approach to Cognitive
E. Amir,* J. Dejong
Artificial Intelligence: Machine Defense Advanced Research Projects Agency,
HR0011-05-1-0040; Information Processing Technology
Learning, Vision, and Robotics Office
Autonomous Car Project The brittleness of first-order symbolic logic has lead to the
E. Amir* (Comput. Sci.), Y. Ma (Elect. & ascension of statistics as the dominant paradigm in AI. But
Comput. Engr.), T. Bretl (Aerosp. Engr.) the statistical paradigm has been unable to support the
Q. Zhang (Ag. & Biol. Engr.) componential knowledge and the rich combinatorial
University of Illinois Department of Computer Science; inference of symbolic logic. Successful cognitive
University of Illinois College of Engineering; University computing will need to combine the power of logic with
of Illinois Department of Electrical & Computer the robustness that underlies statistics. The research in this
Engineering project explores approaches to knowledge representation
and automated reasoning that employ the inferential power
This project will equip a stock car with sensors and of first-order logic but are supported by a new semantics
actuators and will integrate them through software and that embraces the real-world robustness of statistical
special-purpose hardware. The result of the project would inference. The approach that this project develops follows
be an autonomous car that could drive in urban situations a new form of explanation-based learning, and acquires
and could perform tasks such as driving from one place to both EBL concepts and partitioned axiom sets. If
another in town, avoiding obstacles on the road, adhering successful, we believe the research will lead to new
to the proper lanes of traffic, stopping in intersections as algorithms that efficiently appreciate and adapt to their
needed, turning and proceeding in intersections while not
* Denotes principal investigator.
deployment contexts. They will learn quickly to supply a elimination algorithm, FOVE-P, that covers many cases
new user with what is most needed to optimize their joint where atoms share logical variables. The second
problem-solving behavior. contribution is to use FOVE-P for solving the most
probable explanation (MPE) problem, which consists of
Learning Partially Observable Action Models:
calculating the most probable assignment of the random
Efficient Algorithms
variables in a model. The transition from BA to MPE is
E. Amir,* A. Chang, D. Shahaf
straightforward in propositional models, but the lifted first-
Defense Advanced Research Projects Agency (DARPA),
order case is harder. We introduce the notion of lifted
HR0011-05-1-0040; DAF Air Force Research Laboratory
assignments, a distribution of values to a set of random
Award, FA8750-04-2-0222; University of Illinois
variables rather than to each individual one. Lifted
We present tractable, exact algorithms for the effects of assignments are cheaper to compute while being as useful
learning actions and preconditions in partially observable as regular assignments over that group. Both contributions
domains. Our algorithms maintain a propositional logical advance the theoretical understanding of lifted
representation of the set of possible action models after probabilistic inference.
each observation and action execution. The algorithms
Scaling Up First-Order Logical Reasoning with
perform exact learning of preconditions and effects in any
Graphical Structure
deterministic action domain. This includes STRIPS actions
E. Amir,* D. Ramachandran, I. Gammer
and actions with conditional effects. In contrast, previous
[email protected]
algorithms rely on approximations to achieve tractability,
National Science Foundation, IIS 05-46663
and do not supply approximation guarantees. Our
algorithms take time and space that are polynomial in the In this paper we present polynomial-time algorithms that
number of domain features, and can maintain a translate first-order logic (FOL) theories to smaller
representation that stays compact indefinitely. Our propositional encodings than achievable before in
experimental results show that we can learn efficiently and polynomial time. For example, we can sometimes reduce
practically in domains that contain over thousands of the number of propositions to O(|P| + |C|), or O(|P|k · log |
features (more than 21000 states). P|), for |P| predicates of arity k and |C| constant symbols.
The guarantee depends on availability of some graphical
MPE and Partial Inversion in Lifted Probabilistic
structure in the FOL representation. Our algorithms accept
Variable Elimination
all FOL theories, and preserve soundness and
E. Amir,* D. Roth, R. Braz
completeness (sometimes requiring the domain closure
Cycorp; Advanced Research and Development Activity
assumption). Our experiments show significant speedup in
(ARDA) Advanced Question Answering for Intelligence
inference with a SAT solver on real-world problems. Our
(AQUAINT) Program; National Science Foundation,
results address a common approach that translates
ITRIIS-0085980; Defense Advanced Research Projects
inference and decision problems that originate in FOL into
Agency (DARPA), HR0011-05-1-0040
propositional logic, later applying efficient SAT solvers.
It is often convenient to represent probabilistic models in Standard translation techniques result in very large
a first-order fashion, using logical atoms such as partners propositional encodings (O(|P||C|k) for predicates of arity
(X; Y ) as random variables parameterized by logical (k) that are often infeasible to solve. Our approach scales
variables. (de Salvo Braz, Amir, & Roth 2005), following up inference for many objects, and has potential
(Poole 2003), give a lifted variable elimination algorithm applications in planning, probabilistic reasoning, and
(FOVE) for computing marginal probabilities from first- formal verification.
order probabilistic models (belief assessment, or BA).
Domain Knowledge, Explanation-Based Control, and
FOVE is lifted because it works directly at the first-order
Reinforcement Learning
level, eliminating all the instantiations of a set of atoms in
G. DeJong,* A. Laud, Q. Sun, V. Moskovich
a single step, in some cases independently of the number
Office of Naval Research, N00014-01-1-0063
of these instantiations. Previous work could treat only
restricted potential functions. There, the instantiations of Prior research has shown that complex skill-like decision
atoms cannot constrain each other: predicates can appear policies can be acquired by combining an inferential
at most once, or logical variables must not interact across symbolic reasoning with a numeric component. The
atoms. In this paper, we present two contributions. The first approach is called Explanation-Based Control.
one is a significantly more general lifted variable Reinforcement Learning (RL) is a popular machine
* Denotes principal investigator.
learning approach that also automatically acquires skill- techniques capable of handling large numbers of images in
like policies. However, it is difficult or impossible to an efficient and uniform manner.
exploit a domain expert’s knowledge. This means that RL
Toward Category-Level Object Recognition
cannot learn complex policies in an example-efficient
J. Ponce,* Y. LeCun (New York Univ.)
manner. This research explores combining the two
National Science Foundation, IIS-0535152/0535166
approaches to achieve greater example efficiency on the
practical side and a clearer conceptual foundation In cooperation with New York University, Courant
theoretically. Institute
Reasoning about Partially Observed Actions This project addresses the problem of category-level object
M. Nance,* E. Amir, A. Vogel recognition in images. Our aim is to develop effective
DAF Air Force Research Laboratory, FA8750-04-2- 0222 methodologies for three purposes: representing object
classes (a person, a car, a vegetable); learning the
Partially observed actions are observations of action
corresponding object models from cluttered sample images
executions in which we are uncertain about the identity of
in a semi-supervised manner (i.e, the images themselves
objects, agents, or locations involved in the actions (e.g.,
are labeled by the names of the objects they contain, but
we know that action move(?o, ?x, ?y) occurred, but do not
individual pixels and/or image features are not); and
know ?o, ?y). Observed-action reasoning is the problem of
efficiently and robustly recognizing instances of these
reasoning about the world state after a sequence of partial
models in novel images despite clutter, occlusion,
observations of actions and states. In this paper we
viewpoint and illumination changes, and individual
formalize observed-action reasoning, prove intractability
variations within each class.
results for current techniques, and find tractable algorithms
for STRIPS and other actions. Our new algorithms update Toward True 3-D Object Recognition
a representation of all possible world states (the belief J. Ponce*
state) in logic using new logical constants for unknown National Science Foundation, IIS-03-08087
objects. A straightforward application of this idea is This project addresses four fundamental instances of the
incorrect, and we identify and add two key amendments. 3-D object recognition problem: modeling rigid 3-D
We also present successful experimental results for our objects from a small set of unregistered pictures and
algorithm in Blocks-world domains of varying sizes and in recognizing them in cluttered photographs taken from
Kriegspiel (partially observable chess). These results are unconstrained viewpoints; representing and recognizing
promising for relating sensors with symbols, partial- nonuniform texture patterns under nonrigid
knowledge games, multi-agent decision making, and AI transformations; modeling and recognizing articulated
planning. objects in image sequences, with applications to the
ITR: An Integrated Approach to 3-D Photography identification of shots that depict the same scene (shot
Using Shape, Texture, and Motion Cues matching) in video clips; and learning and recognizing
J. Ponce* part-based descriptions of object classes in photographs
National Science Foundation, IIS-03-12438; Beckman and video clips.
Institute for Advanced Science and Technology Large-Scale Temporal Associative Memory
The ability to acquire realistic visual models of complex S. R. Ray,* S. Swarup
3-D scenes from collections of images, known as 3-D University of Illinois
photography, is becoming useful for a wide array of IT The basic problem addressed is to research methods for
applications, including film, game, and Web-content learning to store and recognize a large body of temporal
production, TV advertising, electronic commerce, sequential percepts (presented in any order) utilizing
teleconferencing, and architectural walkthroughs. This neuroscience compatible techniques. Further, the system
project addresses some of the scientific challenges to this must be capable of stable learning and forgetting of
technology. This would involve advances in three research randomly presented samples. In spite of a decade or more
areas: construction of topological mesh models of complex of research in artificial neural networks, temporal sequence
surfaces from weakly-calibrated photographs; automated associative memory is still very poorly understood.
matching and registration of photographs of textured Researchers are studying, analyzing, and simulating a
surfaces taken from different viewpoints; and development number of different models.
of projective and Euclidean structure-from-motion
* Denotes principal investigator.
Model of Superior Colliculus with a Spatiotemporal Context-Sensitive Natural Language Inferences
Neuron Model D. Roth,* A. Carlson
S. R. Ray,* C. Seguin, T. Anastasio National Science Foundation, IIS-9801638; IBM Corp
Defense Advanced Research Projects Agency
The future of intelligent human–machine interaction is in
The superior colliculus is a region of the central nervous the ability to perform context-sensitive inferences. These
system that fuses input data from several modes (visual, are knowledge intensive tasks that are difficult to make
auditory, somatosensory, and so forth) and computer without a significant learning component. This research
orienting output for directing attention, such as head studies a learning approach that targets knowledge
rotation. This project uses a neuron model with trainable intensive language understanding related tasks and directly
temporal response. Spatiotemporal maps are learned by addresses the issue of scalability. It is tailored to large-scale
self-organizing algorithms that simulate known functions processes in terms of data and computation. The approach
of the superior colliculus. The result is expected to have developed can be applied to support a variety of inferences
engineering applications. of the sort required in intelligent human–machine
interactions, as demonstrated in this project by
Neural Network Methods for Temporal Sequence
development of a system that exhibits a wide coverage and
accurate context-sensitive spelling correction.
S. R. Ray,* H. Shah
University of Illinois Inference with Classifiers
D. Roth,* V. Punyakanok
The storage of long temporal vector sequences and their
National Science Foundation, Information Technology
recognition and recall is a subject of considerable interest
Research, IIS-00-85836
both in engineering application and in neuroscience. A new
method for storing long temporal sequences that can be In many situations it is necessary to make decisions that
content-addressed and retrieved from the starting point is depend on the outcomes of several classifiers in a way that
under study. The method applies multilayer "chunking" of provides a coherent inference that satisfies some
invertible vectors in feature map architectures. This constraint. These constraints might arise from the
multilayer method has the potential to store a quantity of sequential nature of the data or other domain specific
distinct sequences in the same elements and to demonstrate constraints. Researchers are studying two general
the property of replay of long experiential memories approaches for this problem and are evaluating those in the
discovered by Wilder Penfield in human subjects some context of an important inference problem in natural
decades ago. language—identifying phrase structure. The first approach
studied is a Markovian approach that extends standard
Self-Aiming Camera
HMMs to allow the use of a rich observation structure and
S. R. Ray,* T. Anastasio, P. Patton
of general classifiers to model state-observation
University of Illinois
dependencies. The second is an extension of constraint
The superior colliculus in vertebrates appears to be a satisfaction formalisms.
primary agent in deciding the direction of saccades and
Intermediate Knowledge Representations that
head-turning actions. Multisensory information, especially
Facilitate Learning
visual, audible, and somatosensory, feeds the two-layer
D. Roth,* S. Agarwal, C. Cumby, W. T. Yih, D. Zimak
neural network that comprises the superior colliculus. This
National Science Foundation, Information Technology
research team has developed and continues to develop
Research, IIS 00-85836; NSF IIS 00-85980; Office of
models of the SC that learn to adapt to variations in the
Naval Research, Multidisciplinary Research Program of
head dimensions and visual/auditory properties. To
the University Research Initiative Award
demonstrate the overall system, including learning,
researchers are constructing a camera and microphone Learning becomes easy once the correct input
system that will supply input to the model SC and respond representation has been chosen. A representation that
to its directives. The camera/microphone system is fully produces linearly separable point sets is an example.
operative on a physically fixed frame. Several projects are aimed at automatically generating
intermediate representations to aid supervised learning
algorithms, developing methods that allow the use of
relational representations and of learning relational
definitions, and developing a flexible knowledge
* Denotes principal investigator.
representation language that can be used along with Learning Theory
feature-efficient learning algorithms. Applications of this D. Roth*
general knowledge representation paradigm are studied in National Science Foundation, IIS-9801638; National
the context of learning in the natural language d

Use: 0.2277