Date( Winter 2006 ) Category Seminar Info 2006/04/25 Faculty Candidate Talk Place: MC437 Time: 9:30 - 10:30 Speaker: Lukasz Golab Affiliation: School of Computer Science, University of Waterloo Title: Sliding Window Query Processing over Data Streams Abstract: Database management systems (DBMSs) have been used successfully in business applications that require persistent storage of relatively static data. However, emerging applications, such as sensor networks, real-time Internet traffic analysis and on-line financial trading, require support for continuous processing of unbounded streams of data. The fundamental assumption of a data stream management system (DSMS) is that new data are generated continually, making it infeasible to store a stream in its entirety. At best, we may be able to maintain a sliding window of recently arrived data. Furthermore, since the contents of a sliding window evolve over time, it makes sense for users to ask a query once and receive updated answers as time goes on. In this talk, I will describe my research on query processing over sliding windows that focuses on two fundamental characteristics of a DSMS: the time-evolving nature of the data and the persistent nature of the queries. Biography of Speaker: Lukasz Golab is a Ph.D. candidate in the School of Computer Science at the University of Waterloo. He holds a B.Sc. in Computer Science from the University of Toronto (2001). During his graduate studies, Lukasz was awarded two NSERC Graduate Scholarships and was one of ten recipients of the Bell Canada 125th Anniversary Graduate Scholarship. Lukasz's research interests include database management issues arising in novel applications, such as data stream processing, data mining and warehousing, and real-time and embedded systems. 2006/04/21 CQIL - Cryptography and Quantum Information Place: MC320 Time: 10:30 - 11:30 Speaker: Jean-Raymond Simard Affiliation: McGill University Area: Cryptography Title: Bit commitment in the two-prover model Abstract: I will first present the two-prover model and the motivation for its use. Then, using this model, I will present a very simple Bit Commitment scheme and prove its security against a quantum adversary. This is joint work with Claude Crépeau, Louis Salvail and Alain Tapp. Biography of Speaker: 2006/04/20 Software Engineering Place: McConnell 103 Time: 10:30 - 11:30 Speaker: Jörg Kienzle Affiliation: McGill University Area: Aspect-Orientated Design Title: Aspect-Oriented Challenge: Implementing the ACID Properties of Transactional Objects Abstract: This talk is an extended version of the talk presented at AOSD 2006 in March. I am going to present an aspect-oriented design of a transaction run-time that ensures the ACID properties (atomicity, consistency, isolation and durability) for transactional objects. A set of ten base aspects is defined, each one providing a well-defined reusable functionality. The base aspects are simple, yet have complex dependencies among each other. The base aspects can be configured and composed in different ways to implement different concurrency control and recovery strategies. This composition is delicate: some aspects conflict with each other, others have to be reconfigured dynamically at run-time. At the end of the talk I want to show how this case study could serve as a benchmark for aspect-oriented software development, in particular for evaluating the expressivity of aspect-oriented programming languages, the performance of aspect-oriented programming environments, and the suitability of aspect-oriented modeling notations. More concretely, I will outline possible master thesis topics that can be built on top of this work. 2006/04/19 Faculty Candidate Talk Place: MC437 Time: 9:30 - 10:30 Speaker: Xue Liu Affiliation: Computer Science Department, University of Illinois at Urbana-Champaign Title: Analysis and Control of Temporal Behavior in Embedded and Networked Computing Systems Abstract: Current software systems are increasing in scale, distribution, and degree of interaction with their environment. Massively distributed embedded systems and multi-stage networked server clusters are two examples. Ensuring performance guarantees in these systems is an important research topic with many practical applications. In this talk, I will present my dissertation work which focuses on efficient analysis and control of temporal behavior in embedded and networked computing systems. First, I will introduce Universal Feasible Region Analysis, a new theoretical schedulability analysis framework for ensuring system schedulability under general workload. Its advantages are scalability for large networks and applicability to arbitrary, fixed-priority scheduling policies. I will illustrate the use of this framework for efficient admission control in networked embedded systems. Then I will present Queueing Model Based Feedback Control, a novel performance management framework for networked server systems. It integrates two separately developed theories--feedback control and queueing theory--into a single analytical framework. Hence it can provide better performance guarantees under dynamic workload compared with previous proposals. To conclude my talk, I will briefly describe my future research plan. Biography of Speaker: Xue Liu is a Ph.D. student in the Computer Science Department at the University of Illinois at Urbana-Champaign, where he is advised by Professor Lui Sha. Xue got his B.S. in Mathematics and M.S. in Automatic Control both from Tsinghua University, China. His research interests are in real-time and embedded systems, networked server performance management, and software reliability. He received the Mavis Memorial Fund Scholarship Award from College of Engineering of UIUC in 2005 for excellent academic performance, research accomplishments, and demonstrated leadership in engineering education and the C. W. Gear Outstanding Graduate Award in 2002 for being the best graduate student from the UIUC Department of Computer Science. He was also recipient of the prestigious Saburo Muroga Fellowship and Ray Ozzie Fellowship. 2006/04/07 CQIL - Cryptography and Quantum Information Place: MC103 Time: 10:30 - 11:30 Speaker: George Savvides Affiliation: McGill University Area: Cryptography Title: Optimal Reductions between Oblivious Transfers using Interactive Hashing Abstract: We present an asymptotically optimal reduction of one-out-of-two String Oblivious Transfer to one-out-of-two Bit Oblivious Transfer using Interactive Hashing in conjunction with Privacy Amplification. Interactive Hashing is used in an innovative way to test the receiver's adherence to the protocol. We show that $(1+\epsilon)k$ uses of Bit OT suffice to implement String OT for $k$-bit strings. Our protocol represents a two-fold improvement over the best constructions in the literature and is asymptotically optimal. We then show that our construction can also accommodate weaker versions of Bit OT, thereby obtaining a significantly lower expansion factor compared to previous constructions. Besides increasing efficiency, our constructions allow the use of any 2-universal family of Hash Functions for performing Privacy Amplification. Of independent interest, our reduction illustrates the power of Interactive Hashing as an ingredient in the design of cryptographic protocols. Joint work with Claude Crepeau. Biography of Speaker: 2006/04/06 Faculty Candidate Talk Place: MC437 Time: 9:15 - 10:15 Speaker: Hongwei Zhang Affiliation: The Ohio State University Title: Dependable Messaging in Sensor Networks Abstract: The sensing, computing, communication, and actuation capabilities of wireless sensor networks are increasingly enabling us to observe and control the physical world. Along with opportunities, sensornets bring challenges to the design of systems dependability. In this talk, I will focus on the challenges in the context of messaging. In sensornets, wireless links tend to be dynamic, both temporally and spatially. Link dynamics are also subject to the impact of application properties such as traffic patterns, which can themselves be dynamic. Thus, a key challenge is how to provide dependable messaging in the presence of link dynamics and varying application properties. To deal with link dynamics and the impact of application traffic patterns, I propose estimating link properties using application data itself rather than periodic control packets. I will discuss the feasibility of data-driven link estimation, its implications to routing protocol design, and its benefits in terms of energy efficiency and network throughput. I will also discuss how the unique application properties of sensornets enable new transport design for delivering bulk bursty data reliably and in real-time. In addition, I will discuss the architectural issues in incorporating application properties in sensornet messaging. Besides messaging, I will briefly discuss the challenge of scalable dependability in large scale networks including not only sensornets but also the Internet. I will conclude with some open problems in building dependable and predictable sensornets and networked embedded systems in general. 2006/04/05 General Place: MC437 Time: 16:00 - 17:00 Speaker: Paul Kruszewski Affiliation: A.I. Implant Area: games, computational geometry Title: Video Games: Not Your Father's Computational Geometry! Applications of computational geometry in ne Abstract: Although computational geometry (CG) has had much success in real-world applications such as chip design, until recently the use of CG in video games has been very limited. The processing power of next-generation video game consoles such as the Xbox 360 and PlayStation 3 has made supercomputing a consumer good. This processor power coupled with the massive city-sized worlds of next-gen games has opened up many opportunities for computational geometers to work in video game development. Biography of Speaker: Dr. Paul Kruszewski is a SOCS graduate, and founder of AI.implant, a leading AI tool & middleware software for game development. 2006/04/04 Faculty Candidate Talk Place: MC437 Time: 9:30 - 10:30 Speaker: Seungjoon Lee Affiliation: Department of Computer Science, University of Maryland Title: Protocol Design under Cooperative and Selfish Settings in Wireless Networks Abstract: Traditional computer networks consist of end-hosts that generate/receive messages and intermediate routers that forward messages. However, in a multihop wireless network, end-hosts must forward messages in order to provide end-to-end connectivity. Constructing a virtual routing backbone is a well-known approach for providing end-to-end connectivity using a subset of nodes; non-backbone nodes can save resources because they do not relay non-local messages or participate in routing. Cooperative nodes voluntarily become backbone nodes as deemed necessary by the backbone formation protocol; however, if nodes are selfish, they join the backbone only if there is sufficient incentive. In this talk, I will present my work in routing backbone construction under both the cooperative and selfish assumptions. An ideal backbone is small, consists of high-capacity nodes, and remains connected when nodes move or fail. Unfortunately, even in a cooperative setting, constructing such a backbone is often infeasible, since some of the desired properties are in conflict (e.g., a small backbone is often too sparse to handle node mobility of failures). I will first describe a new parameterized backbone construction scheme called Trunc-K and explain how to customize a resulting backbone to accommodate performance priorities and operating environments. Next, I will describe how to model and construct a backbone in selfish networks using the notion of a public good. To ensure correct end-to-end forwarding over the backbone, we design a game-theoretic mechanism using the threat of localized punishments and show that each node maximizes its utility when it forwards messages correctly. I will also describe the implementation of the proposed scheme and present experiments from a real IEEE 802.11-based testbed. Biography of Speaker: Seungjoon Lee is a Ph.D candidate in the Department of Computer Science at the University of Maryland. He received his Bachelor's and Master's degrees in Computer Science from Seoul National University, Korea, in 1996 and 2000. He received Dean's Fellowship Award from College of Computer, Mathematical, and Physical Sciences, University of Maryland. He is also a Fellowship recipient from Seoul National University. His research interests include computer networks and distributed systems, and his current focus is on wireless networks, mobile computing, and peer-to-peer systems. 2006/04/03 Faculty Candidate Talk Place: MC437 Time: 9:30 - 10:30 Speaker: Dirk Beyer Affiliation: EPFL, Switzerland Title: Structure Analysis of Large Software Systems Abstract: We present two techniques for structure analysis that scale to large software systems. In the first part, we present CrocoPat, a tool for relational programming. Its language is illustrated on small examples, and some applications to software analysis are explained. The method can be used to formulate graph analysis problems like the detection of instances of design patterns, or the computation of the transitive closure of large relations, in a simple language based on predicate logic. The second part of the talk will emphasis on co-change visualization, a technique for extracting the subsystem structure of a system from the CVS repository. CCVisu is a tool for co-change visualization. It extracts a high-level model of the change history of the software system and produces a visualization that reveals clusters of the system. The layout ensures that artifacts that were often changed together are placed at close positions. 2006/03/28 Faculty Candidate Talk Place: McConnell 437 Time: 9:30 - 10:30 Speaker: Alexandra Fedorova Affiliation: Division of Engineering and Applied Science, Harvard University Title: Operating System Scheduling for Multicore Processors Abstract: Multicore processors, the currently emerging family of microprocessors, run multiple application threads in parallel, and, in contrast with conventional processors, threads share processor resources, such as the second-level cache. Contention for the shared cache may affect how a thread performs. The degree of contention for the cache varies depending on the threads sharing the cache, and, therefore, a thread's performance varies depending on the threads it runs with. A thread scheduler decides how to assign threads to processors in order to achieve goals such as optimal performance or fairness. Scheduling algorithms for multicore processors must take into account the effects of contention for the shared cache in order to work properly. Fair-share scheduling, a popular policy used by many scheduling algorithms, has a desirable property of predictability: given a share of processor's time a thread is expected to complete certain amount of work. I demonstrate that this property is lost if traditional fair-share schedulers are used on multicore processors: a thread's performance varies by as much as 36% depending on the threads it runs with. I present the cache-fair scheduling algorithm - the fair-share scheduling algorithm adapted for multicore processors. This algorithm accounts for the performance effects of contention for the shared cache when making scheduling decisions. My algorithm uses an analytical model to estimate the cache miss rate a thread would have if the cache were shared equally among all the threads, the fair miss rate. It then monitors the behavior of threads at runtime, and if a thread's rate of progress is affected due to the deviation from its fair miss rate, it adjusts the thread's share of CPU cycles proportionately. Introducing the shared cache awareness into the scheduling algorithm results in reducing performance variability by at least a factor of two and by as much as a factor of seven in cases of significant variability. I implemented the cache-fair algorithm in the Solaris operating system, and it works without any advance knowledge about the workload and relies only on hardware performance counters typically available on modern processors. 2006/03/24 Faculty Candidate Talk Place: McConnell 437 Time: 9:15 - 10:15 Speaker: Adam Bargteil Affiliation: Computer Science Department, University of California at Berkeley Title: Computer Animation of Visco-Elasto-Plastic Materials through Physical Simulation Abstract: Computer animation has emerged as an important area of computer science, generating billions of dollars in the film and video game industries and captivating audiences around the world. Physical simulation is an important tool for computer animation because of its ability to generate extremely realistic behaviors of complicated, high degree-of-freedom systems. Simulation of liquids, explosions, and fracture have been used extensively for generating special effects. In this talk, I will present a semi-Lagrangian contouring method for tracking liquid surfaces in fluid simulations. Our method takes the unusual approach of representing the liquid surface explicitly with a polygonal mesh. However, our approach updates the surface in time through an implicit representation, thereby avoiding topological issues. We then extract a new polygonal mesh from this implicit representation. Our technique generates nice looking, very detailed, and temporally coherent surfaces suitable for high-quality computer animation. I will also briefly discuss our methods for simulating the behavior of viscoelastic liquids and elastoplastic solids, such as clay, gels, and mucus. Biography of Speaker: Adam W. Bargteil is a graduating Ph.D. student in computer science at the University of California, Berkeley. His primary research interests are in computer graphics and animation. Adam's thesis work focuses on the problem of tracking liquid surfaces in fluid simulations. A paper describing a portion of this work appeared in the January 2006 issue of ACM Transactions on Graphics. Adam has also co-authored two SIGGRAPH papers: modeling ductile fracture and on modeling viscoelastic fluids. Animated shorts showcasing both of these projects as well as the surface tracking method have appeared in the SIGGRAPH Electronic Theater. He received dual BS degrees in mathematics and computer science (magna cum laude) from the University of Maryland in 2000. Adam was a U.C. Microelectronics Fellow in 2000 and is currently a Siebel Scholar. For the last year, he has been consulting at PDI/DreamWorks, developing fluid simulation tools for a production environment. 2006/03/22 General Place: McConnell 320 Time: 14:30 - 16:00 Speaker: David Poulin Affiliation: University of Queensland and Caltech Area: Quantum Information and Computation Title: Operator Quantum Error Correction: An Overview Abstract: I will describe recent progress in the theory of quantum error correction that goes under the name of operator quantum error correction (OQEC). OQEC builds on known techniques --- standard quantum error correction and noiseless subsystems methods --- to obtain a unified and generalized approach to protect quantum information. I will demonstrate a universal necessary and sufficient condition for a map to be correctable. I will also show how OQEC can be used to substantially simplify existing stabilizer codes, possibly leading to improved threshold for fault-tolerant quantum information processing. Some proof techniques rely on a generalized notion of coherent information and data processing inequality which I will also describe. Biography of Speaker: David obtained a B.S degree from the University of Sherbrooke, did a Master's degree at the University of Montreal with Gilles Brassard, and a Doctoral degree at the University of Waterloo with Raymond Laflamme. He is currently a Postdoctoral Fellow at the University of Queensland and will be taking a new position at Caltech next month. His main interests are quantum error correction, quantum algorithm for the simulation of physical systems, and the interplay between information science and fundamental physics including quantum gravity and the quantum-classical transition. 2006/03/22 Faculty Candidate Talk Place: McConnell 437 Time: 9:30 - 10:30 Speaker: Li-San Wang Affiliation: Department of Biology, University of Pennsylvania Title: Phylogenetic Estimation for Complex Evolutionary Processes Abstract: Stochastic models of sequence evolution, since their introduction in the 1960s, have inspired the development of numerous computational and statistical methods for phylogeny reconstruction which have been widely successful in reconstructing the evolutionary history of genes and species. However, standard evolutionary models have two essential features, both of which are known to fail for a wide range of real biological data: (1) the domain of mutation is a concatenation of multiple independently distributed sites, each following a simple, identical stochastic process, and (2)the evolutionary history is a branching process (tree). This talk is an overview of my research on complex evolutionary processes -- processes that lack either of the two features of standard models. In both cases, new stochastical models need to be developed. Moreover, the inference of evolutionary histories under these models is much harder - in some cases simply computationally more intense, but in other cases posing significant and new algorithmic challenges. I will cover two such processes: the process of gene order evolution and the process of horizontal gene transfer. For each process, I will formulate the estimation problems, identify computational and statistical issues, and present our current results and future research directions. 2006/03/20 Faculty Candidate Talk Place: McConnell 11 Time: 9:30 - 10:30 Speaker: Uri Keich Affiliation: Computer Science Department, Cornell University Title: Estimating the significance of sequence motifs Abstract: Efficient and accurate statistical significance evaluation is an essential requirement for motif-finding tools. One such widely used significance criterion is the p-value of the motif's information content or entropy score. Current computation schemes used in popular motif-finding programs can unwittingly provide poor approximations. We present an approach to a fast and reliable estimation of this p-value that can be applied more generally. We then show that in the context of twilight zone searches, or searches for relatively weak motifs, the paradigm of relying on entropy scores and their p-values can surprisingly lead to undesirable results. These lead us to consider alternative approaches to analyze the significance of motifs. 2006/03/14 Faculty Candidate Talk Place: McConnell 437 Time: 9:30 - 10:30 Speaker: Jennifer Neville Affiliation: Department of Computer Science, University of Massachusetts Title: From Nodes to Networks: Exploiting Autocorrelation to Improve Statistical Models of Relational Data Abstract: Statistical relational learning is transforming the field of automated learning and discovery by moving beyond the conventional analysis of entities in isolation to analyze networks of interconnected entities. In domains such as bioinformatics, citation analysis, epidemiology, fraud detection, intelligence analysis, and web analytics, there is often limited information about any one entity in isolation, instead it is the connections among entities that are of crucial importance to pattern discovery. One of the most compelling reasons to use relational models is the ubiquitous presence of autocorrelation in relational datasets. Autocorrelation is a statistical dependency between the values of the same variable of related entities (e.g., hyperlinked web pages are likely to discuss the same topic), which can be exploited to improve predictions by learning models for collective inference. In this talk, I will discuss two graphical models I have developed for collective inference: relational dependency networks (RDNs) and latent group models (LGMs). RDNs are the first statistical relational model capable of learning cyclic autocorrelation dependencies. LGMs models are the first model to exploit latent group structures to improve inference accuracy and efficiency. To understand the performance differences between RDNs and LGMs, I have developed an extended bias-variance analysis framework that incorporates errors due to both learning and inference. Using this framework, I will demonstrate the effects of data characteristics on model performance and illustrate the mechanisms behind model performance that can be used to drive the development of improved models and algorithms. Biography of Speaker: Jennifer Neville is a PhD candidate in the Department of Computer Science at the University of Massachusetts Amherst working with Professor David Jensen in the Knowledge Discovery Laboratory. Her research focuses on data mining and machine learning in relational data, with applications in bioinformatics, citation analysis, epidemiology, fraud detection, and web analytics. Jennifer received her B.S. with honors in 2000 and her M.S. in 2004 from the University of Massachusetts Amherst. She was awarded graduate research fellowships by both NSF and AT&T Laboratories. 2006/03/08 Faculty Candidate Talk Place: McConnell 437 Time: 9:30 - 10:30 Speaker: Colin Dewey Affiliation: University of California, Berkeley Area: Bioinformatics Title: Whole-genome alignments and polytopes for comparative genomics Abstract: Whole-genome sequencing of many species has presented us with the opportunity to deduce the evolutionary relationships between each and every nucleotide. In this talk, I will present algorithms for this problem, which is that of multiple whole-genome alignment. The sensitivity of whole-genome alignments to parameter values can be ascertained through the use of alignment polytopes, which will be explained. I will also show how whole-genome alignments are used in comparative genomics, including the identification of novel genes, the location of micro-RNA targets, and the elucidation of cis-regulatory element and splicing signal evolution. Biography of Speaker: Colin Dewey was an undergraduate at the University of California, Berkeley, where he majored in Electrical Engineering and Computer Sciences with an honors breadth area in Molecular Biology. After receiving his B.S. with high honors in 2001, he continued on as a graduate student at Berkeley under the guidance of Lior Pachter. He will receive his Ph.D. in Electrical Engineering and Computer Sciences with a Designated Emphasis in Computational and Genomic Biology in May 2006. 2006/03/03 General Place: MC103 Time: 10:30 - 11:30 Speaker: Patrick Hayden Affiliation: McGill University Area: Cryptography and Quantum Information Title: The classical and quantum private capacities of a secret shared Cartesian frame Abstract: A private shared Cartesian frame is a novel form of private shared correlation that allows for both private classical and quantum communication. Cryptography using a private shared Cartesian frame has the remarkable property that asymptotically, if perfect privacy is demanded, the private classical capacity is three times the private quantum capacity. We demonstrate that if the requirement for perfect privacy is relaxed, then it is possible to use the properties of random subspaces to nearly triple the private quantum capacity, almost closing the gap between the private classical and quantum capacities. Joint work with Stephen Bartlett and Rob Spekkens. 2006/03/03 Faculty Candidate Talk Place: McConnell 437 Time: 9:30 - 10:30 Speaker: Aseem Agarwala Affiliation: Department of Computer Science and Engineering, University of Washington Area: Graphics Title: Beyond the traditional image: depicting reality by merging multiple photographs and videos Abstract: Digital cameras, which replace film with a combination of a digital image sensor and a computer, have mostly been designed to mimic their analog antecedents. The flexibility and power of digital processing, however, offers the potential to move far beyond the capabilities of traditional cameras and produce much more expressive and communicative depictions of the world around us. One way to explore this potential is to capture multiple photographs and/or videos and combine them into enhanced depictions that are better than any of the originals; in this talk I will discuss several projects that take this approach. The "photomontage" system is an interactive tool that partially automates the process of combining the best features of a stack of images. The "panoramic video texture" is a new medium that combines the benefits of panoramic photography and video to provide a more immersive depiction of a scene. Finally, "multi-viewpoint panoramas" extend the medium of panoramic photography to incorporate information from multiple, shifted viewpoints in order to depict very long scenes such as the buildings along the side of a city street. I will conclude by discussing future directions for research in digital photography and video. 2006/02/27 Faculty Candidate Talk Place: McConnell 437 Time: 9:30 - 10:30 Speaker: Jeffrey Nichols Affiliation: Human-Computer Interaction Institute, School of Computer Science, Carnegie Mellon University Area: Human Computer Interaction Title: Automatically Generating High-Quality User Interfaces for Appliances Abstract: The number and diversity of computerized appliances in our homes and offices is greatly increasing. These appliances are well-known for being difficult to use, in part because manufacturers want to support many features while economizing on buttons and screens. This leads to multiple independent functions being overloaded on a single button and user feedback that consists of beeps to indicate success and failure. Each appliance interface also has its own idiosyncrasies, which means that learning to use a particular appliance from one manufacturer often does not help when learning to use a similar appliance from a different manufacturer. In this talk, I present the Personal Universal Controller (PUC) framework, which moves appliance interfaces from the physical appliance to a handheld device that the user is already carrying, such as a personal digital assistant (PDA) or mobile phone. I will focus on the PUC framework's ability to automatically generate personally consistent interfaces that take into account interfaces that the user has previously encountered, which addresses the problem of idiosyncratic interfaces. I will conclude with a brief discussion of how this work might be applied to improve user interfaces in other domains. Biography of Speaker: Jeffrey Nichols is a doctoral student in the Human-Computer Interaction Institute in Carnegie Mellon University's School of Computer Science, where he is advised by Brad Myers. He is the lead researcher on the Personal Universal Controller project, exploring how handheld computers can improve the usability of household and office appliances. He received a BS degree in computer engineering from the University of Washington in 2000.