Quick links

CS Department Colloquium Series

Precise and Fully-Automatic Verification of Container-Manipulating Programs

Date and Time
Tuesday, April 5, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
David Walker
One of the key challenges in automated software verification is obtaining a conservative, yet sufficiently precise understanding of the contents of data structures in the heap. A particularly important and widely-used class of heap data structures is containers, which support operations such as inserting, retrieving, removing, and iterating over elements. Examples of containers include arrays, lists, vectors, sets, maps, stacks, queues, etc.

In this talk, I will describe a sound, precise, scalable, and fully-automatic static analysis technique for reasoning about the contents of container data structures. This technique is capable of tracking position-value and key-value correlations, supports reasoning about arbitrary nestings of these data structures, and integrates container reasoning directly into a heap analysis, allowing, for the first time, the verification of complex programs that manipulate heap objects through container data structures. More specifically, I will describe a symbolic heap abstraction that augments a graph representation of the heap with logical formulas and that reduces some of the difficulty of heap reasoning to standard logic operations, such as existential quantifier elimination and satisfiability. I will present experimental results demonstrating that our technique is very useful for verifying memory safety in complex heap- and container-manipulating C and C++ programs that use arrays and other container data structures from the STL and QT libraries.

Isil Dillig is a PhD candidate at the Computer Science Department at Stanford University, advised by Prof. Alex Aiken. Her research interests include software verification, static analysis, and constraint solving. Isil received her undergraduate degree from Stanford in 2006, with a major in computer science with honors and distinction. She is the recipient of Frederick Emmons Terman Engineering Scholastic Award at Stanford, as well as the recipient of Forbes School of Engineering and Stanford Graduate Fellowships.

Differential Privacy: Recent Developments and Future Challenges

Date and Time
Wednesday, March 30, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Guy Rothblum, from Princeton University
Host
Sanjeev Arora
Consider a database of sensitive information about a set of participants. Statistical analysis of the data may yield valuable results, but it also poses serious threats to participants' privacy. A successful research program has, in the last few years, attempted to address these conflicting concerns. This line of work formulated the rigorous privacy guarantee of differential privacy [Dwork McSherry Nissim and Smith '06] and showed that, in some cases, data analyses can provide accurate answers while protecting participants' privacy.

I will review some of this past work, and then introduce new general-purpose tools for privacy preserving data analysis: 1. A "multiplicative weights" framework for fast and accurate differentially private algorithms. 2. New privacy analysis techniques, including robust privacy guarantees for differential privacy under composition.

We will use these tools to show that differential privacy permits surprisingly rich and accurate data analyses. I will then highlight some of the intriguing challenges that remain open for future work in this field.

No prior knowledge will be assumed.

Guy Rothblum is a postdoctoral research fellow at Princeton University, supported by a Computing Innovation Fellowship. He completed his Ph.D. in computer science at MIT, advised by Shafi Goldwasser. His research interests are in theoretical computer science, especially privacy-preserving data analysis, cryptography and complexity theory.

Beyond Naming: Image Understanding via Physical, Functional and Causal Relationships

Date and Time
Wednesday, March 23, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Thomas Funkhouser
What does it mean to "understand" an image? One popular answer is simply naming the objects seen in the image. During the last decade most computer vision researchers have focused on this "object naming" problem. While there has been great progress in detecting things like "cars" and "people", such a level of understanding still cannot answer even basic questions about an image such as "What is the geometric structure of the scene?", "Where in the image can I walk?" or "What is going to happen next?". In this talk, I will show that it is beneficial to go beyond mere object naming and harness relationships between objects for image understanding. These relationships can provide crucial high-level constraints to help construct a globally-consistent model of the scene, as well as allow for powerful ways of understanding and interpreting the underlying image. Specifically, I will present image and video understanding systems that incorporate: (1) physical relationships between objects via a qualitative 3D volumetric representation; (2) functional relationships between objects and actions via data-driven physical interactions; and (3) causal relationships between actions via a storyline representation. I will demonstrate the importance of these relationships on a diverse set of real-world images and videos.

Abhinav Gupta is a postdoctoral fellow at the Robotics Institute, Carnegie Mellon University working with Alexei Efros and Martial Hebert. His research is in the area of computer vision, and its applications to robotics and computer graphics. He is particularly interested in using physical, functional and causal relationships for understanding images and videos. His other research interests include exploiting relationship between language and vision, semantic image parsing, and exemplar-based models for recognition. Abhinav received his PhD in 2009 from the University of Maryland under Larry Davis. His dissertation was nominated for the ACM Doctoral Dissertation Award by the University of Maryland. Abhinav is a recipient of the ECCV Best Paper Runner-up Award(2010) and the University of Maryland Dean's Fellowship Award (2004).

Next generation sequence characterization of complex genome structural variation

Date and Time
Tuesday, March 22, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Olga Troyanskaya
Structural variation, in the broadest sense, is defined as the genomic changes among individuals that are not single nucleotide variants. Rapid computational methods are needed to comprehensively detect and characterize specific classes of structural variation using next-gen sequencing technology. We have developed a suite of tools using a new aligner, mrFAST, and algorithms focused on the characterization of structural variants that have been more difficult to assay : (i) deletions, small insertions, inversions and mobile element insertions using read-pair signatures (VariationHunter), (ii) novel sequence insertions coupling read-pair data local sequence assembly (NovelSeq), (iii) absolute copy number of duplicated genes using read-depth analysis coupled with single-unique nucleotide (SUN) identifiers. I will present a summary of our results of 9 high-coverage human genomes regarding these particular classes of structural variation compared to other datasets. In particular, I will also summarize our read-depth analysis of 159 low-coverage human genomes for copy number variation of duplicated genes. We use these data to correct CNV genotypes for copy number and location and discover previously hidden patterns of complex polymorphism. Our results demonstrate, for the first time, the ability to assay both copy and content of complex regions of the human genome, opening these regions to disease association studies and further population and evolutionary analyses. The algorithms we have developed will provide a much needed step towards a highly reliable and comprehensive structural variation discovery framework, which, in turn will enable genomics researchers to better understand the variations in the genomes of newly sequenced human individuals including patient genomes.

Can Alkan is currently a Senior Fellow in Professor Evan E. Eichler's group in the Department of Genome Sciences at the University of Washington. His current work includes computational prediction of human structural variation, and characterization of segmental duplications and copy-number polymorphisms using next generation sequencing data. He graduated from Bilkent University Dept. of Computer Engineering in 2000, and received his Ph.D. in Computer Science from Case Western Reserve University in 2005. During his Ph.D. he worked on the evolution of centromeric DNA, RNA-RNA interaction prediction and RNA folding problems.

Towards a Highly Available Internet

Date and Time
Monday, March 28, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Jennifer Rexford
Internet availability -- the ability for any two nodes in the Internet to communicate — is essential to being able to use the Internet for delivery critical applications such as real-time health monitoring and response. Despite massive investment by ISPs worldwide, Internet availability remains poor, with literally hundreds of outages occurring daily, even in North America and Europe. Some have suggested that addressing this problem requires a complete redesign of the Internet, but in this talk I will argue that considerable progress can be made with a small set of backwardly compatible changes to the existing Internet protocols. We take a two-pronged approach. Many outages occur on a fine-grained time scale due to the convergence properties of BGP, the Internet’s interdomain routing system. We describe a novel set of additions to BGP that retains its structural properties, but applies lessons from fault tolerant distributed systems research to radically improve its availability. Other outages are longer-lasting and occur due to complex interactions between router failures and router misconfiguration. I will describe some ongoing work to build an automated system to quickly localize and repair these types of problems.

Thomas Anderson is the Robert E. Dinning Professor of Computer Science and Engineering at the University of Washington. His research interests span all aspects of building practical, robust, and efficient computer systems, including distributed systems, operating systems, computer networks, multiprocessors, and security. He is an ACM Fellow, winner of the ACM SIGOPS Mark Weiser Award, winner of the IEEE Bennett Prize, past program chair of SIGCOMM and SOSP, and he has co-authored seventeen award papers.

Learning Hierarchical Generative Models

Date and Time
Thursday, March 24, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
David Blei
Building intelligent systems that are capable of extracting meaningful representations from high-dimensional data lies at the core of solving many Artificial Intelligence tasks, including visual object recognition, information retrieval, speech perception, and language understanding. My research aims to discover such representations by learning rich generative models which contain deep hierarchical structure and which support inferences at multiple levels.

In this talk, I will introduce a broad class of probabilistic generative models called Deep Boltzmann Machines (DBMs), and a new algorithm for learning these models that uses variational methods and Markov chain Monte Carlo. I will show that DBMs can learn useful hierarchical representations from large volumes of high-dimensional data, and that they can be successfully applied in many domains, including information retrieval, object recognition, and nonlinear dimensionality reduction. I will then describe a new class of more complex probabilistic graphical models that combine Deep Boltzmann Machines with structured hierarchical Bayesian models. I will show how these models can learn a deep hierarchical structure for sharing knowledge across hundreds of visual categories, which allows accurate learning of novel visual concepts from few examples.

Ruslan Salakhutdinov received his PhD in computer science from the University of Toronto in 2009, and he is now a postdoctoral associate at CSAIL and the Department of Brain and Cognitive Sciences at MIT. His research interests lie in machine learning, computational statistics, and large-scale optimization. He is the recipient of the NSERC Postdoctoral Fellowship and Canada Graduate Scholarship.

Deep Semantics from Shallow Supervision

Date and Time
Wednesday, April 6, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Host
David Blei
What is the total population of the ten largest capitals in the US? Building a system to answer free-form questions such as this requires modeling the deep semantics of language. But to develop practical, scalable systems, we want to avoid the costly manual annotation of these deep semantic structures and instead learn from just surface-level supervision, e.g., question/answer pairs. To this end, we develop a new tree-based semantic representation which has favorable linguistic and computational properties, along with an algorithm that induces this hidden representation. Using our approach, we obtain significantly higher accuracy on the task of question answering compared to existing state-of-the-art methods, despite using less supervision.

Percy Liang obtained a B.S. (2004) and an M.S. (2005) from MIT and is now completing his Ph.D. at UC Berkeley with Michael Jordan and Dan Klein. The general theme of his research, which spans machine learning and natural language processing, is learning richly-structured statistical models from limited supervision. He has won a best student paper at the International Conference on Machine Learning in 2008, received the NSF, GAANN, and NDSEG fellowships, and is also a 2010 Siebel Scholar.

Designing Maps to Help People

Date and Time
Wednesday, March 2, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Host
Thomas Funkhouser
Over the last 15 years spatial databases and mapping services have become one of the most important applications on the Internet. In that time we have seen transformative increases in the availability of spatial data such as detailed satellite, streetside and casual images, 3D terrain and building models, and real-time traffic information. Such data has made it possible to create a variety of new kinds of maps and online experiences of any location on earth. Yet, only a handful of different kinds of maps are available online today. Moreover, it is not always clear what task today's online maps are designed to solve.

In this talk I'll present a user-centered view of map design. I'll describe some of the difficult spatial tasks people regularly face as they navigate the world and I'll draw on the long history of mapmaking to show a variety of maps that are carefully designed to address these tasks. Examples will include maps designed to help users find their way from one location to another, to aid viewers in better understanding the spatial layout of 3D environments, and to assist tourists in finding points of interest in a new city. I'll conclude with a set of open challenges for online map design.

Maneesh Agrawala is an Associate Professor in Electrical Engineering and Computer Science at the University of California, Berkeley. He received a B.S. in 1994 and a Ph.D. in 2002, both from Stanford University. Maneesh works on visualization, computer graphics and human computer interaction. His focus is on investigating how cognitive design principles can be used to improve the effectiveness of visual displays. The goals of this work are to discover the design principles and then instantiate them in both interactive and automated design tools. Recent projects based on this methodology include automated map design algorithms, systems for designing cutaway and exploded view illustrations of complex 3D objects, and interactive tools for manipulating digital photographs and video. He received an Okawa Foundation Research Grant in 2006, an Alfred P. Sloan Foundation Fellowship, an NSF CAREER award in 2007, the SIGGRAPH Significant New Researcher award in 2008 and MacArthur Foundation Fellowship in 2009.

Formal Verification of Software Infrastructure: From Science to Engineering

Date and Time
Tuesday, March 8, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Speaker
Host
David Walker
Is there anything to be done about the low reliability of software systems? Formal verification has already become part of standard practice in some domains where the cost of failure is especially high. Can the cost of verification be brought low enough that we can make it part of the standard development process for our servers, desktops, and so on? This talk summarizes my experience addressing this question through formal, machine-checked proof about some of the key low-level pieces of software systems.

I will discuss work in verifying the correctness of compilers and of low-level software like memory management and thread scheduling libraries. In each case, practical solutions have required both the "science" of choosing the right mathematical abstractions to frame the problem and the "art" of proof engineering to support code re-use and automation in proofs. Both of the examples I will discuss rely critically for their "science" pieces on higher-order logic, which allows logical quantifiers to range over functions and predicates, rather than just the basic mathematical objects supported by first-order logic. The "art" piece applies in dealing with the undecidability of the very expressive theories that are natural for these problems. My work has demonstrated the practicality of verification using expressive higher-order specifications, lowering the human cost of verification by an order of magnitude or more for several important kinds of software infrastructure.

Adam Chlipala's research applies computer theorem-proving and type systems to problems throughout the software stack, from assembly to high-level, higher-order languages. His focus is reducing the human cost of mathematically rigorous assurance about software. He finished his PhD at Berkeley in 2007, with a thesis on compiler verification for higher-order source languages. Since starting as a postdoc at Harvard, he has continued that line of work, as well as getting involved with semi-automated correctness verification for imperative programs via separation logic, first with the Ynot project, which focuses on high-level functional programs, and more recently with the Bedrock project, which deals with assembly-level reasoning. Adam also has a longstanding interest in web application programming, including the development of several domain-specific languages. Through his company Impredicative LLC, he has recently gotten involved in consulting based on his latest web language Ur/Web.

Systems and Algorithms for Computational Photography

Date and Time
Monday, February 28, 2011 - 4:30pm to 5:30pm
Location
Computer Science Small Auditorium (Room 105)
Type
CS Department Colloquium Series
Host
Szymon Rusinkiewicz
Digital cameras have become one of the most ubiquitous forms of computer in existence, but we still don't have a good handle on how to program them, what data we should program them to capture, how that data should be combined to make the photograph, and if a photograph is even the desired output. I'll talk about two of the tools we've developed to explore these questions.

The first is the "Frankencamera", which is an open API and architecture for programmable cameras that makes it easy to deterministically control the various components of a camera at high frame rates. The goal of the Frankencamera is to enable research in photography, and indeed in graduate-level classes we've found that students equipped with this API are much more able to prototype their novel camera applications than with conventional camera APIs.

The second tool is the discrete Gauss transform, which represents a class of algorithms that are widely used in photographic image processing for denoising, sharpening, and controlling tone and contrast. Incarnations of the discrete Gauss transform include the bilateral filter, the joint bilateral filter, and non-local means. We'll talk about making discrete Gauss transforms fast by representing the problem as resampling in a higher-dimensional space. Finally, time permitting, I'll talk about what we need to do to get these kinds of photographic image processing algorithms to run efficiently on the agglomeration of processors found inside today's cameras.

Andrew Adams is a PhD student working with Marc Levoy at Stanford University. His research interests include computational cameras, fast image processing, and more generally languages and APIs that simplify complex domains. Andrew received a BS in Computer Science and Mathematics from the University of New South Wales in Australia in 2004, and an MS in Computer Science from Stanford in 2006. He has also worked on the Google Streetview project, and collaborates closely with Nokia Research on computational photography. Andrew also enjoys teaching, and has won several teaching awards.

Follow us: Facebook Twitter Linkedin