CS Department Colloquium Series

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.

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).

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.

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.

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.

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.

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.

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.

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.

The Internet is the underlying fabric for nearly all of our day-to-day communication; it is an undeniable success. More than a billion people around the world now have Internet access, and that number is projected to at least double in the next 10 years. The Internet is seeing increasing penetration in various resource-challenged environments, both in this country and abroad. These new frontiers for networking offer exciting opportunities, but they also pose serious challenges. Internet attacks are proliferating. Networks are becoming increasingly complex and difficult to troubleshoot. More than 20 countries around the world censor at least some Internet content. Our personal and private data is falling into the hands of a few large content providers. The performance of networks in homes, and how humans interact with them, are both poorly understood. These coming challenges will require us to think differently about networking: a discipline that has focused almost exclusively on performance must begin thinking more about people.

In this talk, I will take a retrospective view of some important networking innovations over the past 10 years, surveying some solutions we and others have developed to improve the Internet's security, manageability and availability. I will then take a look forward at new challenges, and argue that to solve the most pressing problems for networking today, we must draw on techniques from a broad range of areas, including policy, economics, programming languages and human-computer interaction.

Nick Feamster is an assistant professor in the College of Computing at Georgia Tech. He received his Ph.D. in Computer science from MIT in 2005, and his S.B. and M.Eng. degrees in Electrical Engineering and Computer Science from MIT in 2000 and 2001, respectively. His research focuses on many aspects of computer networking and networked systems, including the design, measurement, and analysis of network routing protocols, network operations and security, and anonymous communication systems. In December 2008, he received the Presidential Early Career Award for Scientists and Engineers (PECASE) for his contributions to cybersecurity, notably spam filtering. His honors also include a Sloan Research Fellowship, the NSF CAREER award, Technology Review's TR35 award, the IBM Faculty Fellowship, and award papers at SIGCOMM 2006, the NSDI 2005 conference, Usenix Security 2002 and Usenix Security 2001.