CIS Seminars & Events

Spring 2007

Tuesday, February 27, 2007
Adrien Treuille
Computer Science Dept Computer Graphics, University of Washington
"New approaches to modeling and control of complex dynamics"

Read the Abstract

Abstract: Complex phenomena such as animal morphology, human motion, and large fluid systems challenge even our most sophisticated simulation and control techniques. My overarching research goal has been to develop fundamentally new methods to approach such high-dimensional and nonlinear problems. This talk presents my work solving these problems across a wide range of phenomena, including a new model-reduction approach to fluids that is orders-of-magnitude faster than standard simulation methods and enables interactive high-resolution fluid simulation for the first time. Another example is a continuum approach to crowd dynamics which efficiently reproduces empirical aspects of large crowd behavior that would be difficult or impossible to achieve with traditional agent models. The talk will also cover work on several other phenomena including human animation, animal morphology, and protein folding. Such new algorithmic approaches advance not only our ability to simulate and control complex systems but also our

Tuesday, March 27, 2007
Alla Safonova
Computer Graphics Lab
Carnegie Mellon University
"Synthesizing Human Motion from Intuitive Constraints"

Read the Abstract

Abstract: My work enables users to create complex and realistic animation by providing a small amount of information. For example, a human animation might be specified by posing an articulated doll or sketching a path through a complex environment. The two algorithms I have developed can automatically create natural-looking human motion that matches this specification.  The key insight behind both approaches is to build a compact representation of human motion based on available human motion capture data. The first approach builds a continuous low-dimensional representation, while the second builds a discrete representation consisting of only natural poses. The compactness of these representations allows an optimizer to efficiently find a solution that matches the user's specification. In addition, these representations favor natural poses and velocities, which biases the optimizer towards natural-looking solutions---an objective that is very hard to define mathematically. In my talk, I will compare and demonstrate the effectiveness of these two approaches in synthesizing natural, physically realistic, complex motions sketched using a simple interface.

Thursday, April 5, 2007
Stephen Boyd
Information Systems Laboratory, Department of Electrical Engineering, Stanford University
"An Interior-Point Method for Large-Scale l_1-Regularized Logistic Regression"

Read the Abstract

Abstract: Logistic regression with l_1 regularization has been proposed as a promising method for feature selection in classification problems. In this paper we describe an efficient interior-point method for solving large-scale l_1-regularized logistic regression problems. Small problems with up to a thousand or so features and examples can be solved in seconds on a PC; medium sized problems, with tens of thousands of features and examples, can be solved in tens of seconds (assuming some sparsity in the data). A variation on the basic method, that uses a preconditioned conjugate gradient method to compute the search step, can solve very large problems, with a million features and examples (e.g., the 20 Newsgroups data set), in a few tens of minutes, on a PC. Using warm-start techniques, a good approximation of the entire regularization path can be computed much more efficiently than by solving a family of problems independently. Joint work with Kwangmoo Koh and Seung-Jean Kim

Thursday, April 19, 2007
Vivek Kwatra
Department of Computer Science, The University of North Carolina at Chapel Hill
"Spatio-temporal Textural Modeling for Data-driven Synthesis and Visualization"

Read the Abstract

Abstract: With the increased accessibility of capture devices and techniques, rich amounts of real-world data is available to us in various forms including images, video, 3D models, motion capture, weather patterns, etc. On the other hand, one of the primary goals in computer graphics has been to synthesize this data from first principles either through simulation or user interaction. My research goal has been to develop synthesis-friendly models from spatio-temporal data that not only exploit the richness of real data, but also afford the controllability of simulation and interaction.

In this talk, I will focus on synthesis methods that treat visual as well as dynamic data as texture. Such textural modeling is especially conducive for controllable synthesis because of its locality in space and time. I will first demonstrate a technique that allows for spatio-temporal extension of image and video data, and combined with intelligent user interfaces, can be used for computational photography applications such as smart image compositing and storyboarding. I will then describe a more flexible texture model that can be used to augment fluid simulation with appearance and shape textures to generate complex fluid effects such as ripples and foam in turbulent flow and patterns in the crust of flowing lava. I will also show how we can incorporate physical and geometric characteristics of the flow into the synthesis process in a temporally coherent manner. This technique, besides adding to the visual realism of the simulated fluid, also provides a handy visualization tool that lays bare significant features on the surface of the flowing fluid, which may not be apparent otherwise.

Monday, April 23 , 2007
Judea Pearl
Department of Computer Science
University of California, Los Angeles
"The Mathematics of Casual Inference"

Read the Abstract

Abstract: I will review concepts, principles, and mathematical tools that were found useful in applications involving causal relationships.  The principles are based on structural-model semantics, in which functional (or counterfactual) relations represent autonomous physical processes. This semantical framework, enriched with a few ideas from logic and graph theory, gives rise to a complete, coherent, and friendly calculus of causation that unifies the graphical and counterfactual approaches to causation and resolves long-standing problems in several of the sciences. These include questions of confounding, causal effect estimation, policy analysis, legal responsibility, effect decomposition, instrumental variables, and the integration of data from diverse studies.

Reference: J. Pearl, Causality (Cambridge University Press, 2000)


Tuesday, April 24, 2007
Lior Pachter
Mathematics and Computer Science, University of California at Berkeley
(On sabbatical at the Mathematical Institute and the Department of Statistics, University of Oxford)
"From Drosophila and Transposable Elements to the Neighbor-Net  Algorithm and Phylogenetic Networks"

Read the Abstract

Abstract: We begin with an overview of the Drosophila genome project, whose  goal is the sequencing and comparison of 12 fruit fly genomes. In  particular, we discuss transposable elements. These are self- replicating sequences that play a major role in shaping the structure  and function of genomes. Our methods for studying transposable  elements lead naturally to the analysis of split systems and their  associated phylogenetic networks. We discuss various aspects of the  neighbor-net algorithm, which is a widely used method for obtaining  phylogenetic networks from split systems. We show that neighbor-net  is a greedy algorithm for the traveling-salesman problem and explain  its connection to the popular neighbor-joining algorithm. We also  prove that neighbor-net is statistically consistent, and in doing so  obtain a new proof that the traveling-salesman problem can be solved  in polynomial time for Kalmanson matrices. This result is closely  related to results we have recently obtained on the robustness of the  neighbor-joining algorithm. Our application of neighbor-net to the  split system we obtain from transposable elements in Drosophila  reveals interesting insights about a set of species that may have  undergone lineage sorting. This is joint work with Anat Caspi, Dan Levy, and Radu Mihaescu.

Wednesday, April 25th, 2007
Franklin Institute Symposium Lecture
Dr. Stuart Card
Senior Research Fellow, Palo Alto Research Center
Sponsor:  Prof. Beth Adelson, Rutgers University
"Human Information Interaction:  The theory and design of cognitive prostheses"

Read the Abstract

Abstract: A colloquium to honor Stuart Card, recipient of the 2007 Bower Award and Prize for Achievement in Science in Human-Centered Computing

Supported by The Franklin Institute; the Department of Computer and Information Science,
School of Engineering and Applied Science, University of Pennsylvania; the Institute for Research in Cognitive Science.

"Information is central to humans and their institutions.  Just as machines augmented human perceptual and physical powers, machines now make us smarter individually and sometimes even in groups.  How can we formulate principles of design for such machines, so that their success is more than hit or miss?  It is important that we do so, since there is evidence that a new and more potent wave of capabilities and impacts lies just ahead."

For more information about  Dr. Card’s work and the Bower Award in Human-Centered computing contact Professor Beth Adelson:

Tuesday, May 29, 2007
Luca Cardelli
Microsoft Research
"Artificial Biochemistry"

Read the Abstract

Abstract: Systems Biology is a new discipline aiming to understand the behavior of biological systems as it results from the (non-trivial, "emergent") interaction of biological components. In addition to analyzing existing biological networks to understand their function, it is also important to understand from the ground up what simple networks of interacting components "can do". That investigation can be carried out in abstract "artificial" frameworks, as long as the ground rules are kept close enough to the ones of biochemistry. We discuss some biologically inspired networks that are characterized by simple components, but by complex interactions. Subtle and unexpected behavior emerges even from simple circuits, and yet stable behavior emerges too, giving some hints about what may be critical and what may be irrelevant in the organization of biological networks.

Monday, July 30, 2007
Shaz Qadeer
Microsoft Research
"Iterative context-bounding: a new approach for finding errors in large multithreaded programs"

Read the Abstract

Abstract: Multithreaded programs are difficult to get right.  The interaction of concurrently executing threads leads to a huge number of program behaviors.  Programmers, unable to account for all possible interactions among threads, often make errors which are difficult to find by traditional testing methods.  In this lecture, I will present CHESS, a software model checker for systematically enumerating such behaviors.

CHESS implements iterative context-bounding, a new approach for effectively searching the state space of a multithreaded program.  In an execution of a multithreaded program, a context switch occurs when a thread temporarily stops execution and a different thread starts.  Iterative context-bounding gives priority to executions with fewer context switches, exploring all executions with no context switches followed by all executions with one context switch and so on.

For a fixed number of context switches, the total number of executions in a program is polynomial in the number of steps taken by each thread.  This theoretical upper bound makes it practically feasible to scale systematic exploration to large programs without sacrificing the ability to go deep in the state space.  Our experience applying CHESS to large real-world programs shows that systematic search with a small number of context switches has the ability to expose nontrivial concurrency bugs.  CHESS has uncovered 9 previously unknown bugs in our benchmarks, each exposed by an execution with at most 2 context switches.