- talks - lists.cs.princeton.edu

Y Zhang preFPO
by Melissa Lawson 25 Mar '11

25 Mar '11

Yun Zhang will present her preFPO on Friday April 1 at 2PM in Room 301. The members of her committee are: David August, advisor; David Walker and Scott Mahlke (Michigan), readers; Doug Clark and Jen Rexford, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ----------------------------------- Title: Decouple Redundant Execution for Transient Fault Tolerance Abstract: As semiconductor technology continues to scale, transient faults are emerging as a critical reliability concern in modern microprocessors. The increasing density of transistors on chip, reduced noise margin of each transistor, and voltage scaling are making chips more susceptible to transient faults than ever. Both hardware or software solutions have been proposed for transient fault detection and recovery. The hardware approach adds redundant hardware modules to the system, thus requiring extra chip area as well as hardware design and veri?cation cost. In addition, the scope and mechanism of fault tolerance are hardwired at design time, which could be suboptimal depending on deployment environment. Software-only solutions do not require any specialized hardware extensions and are more ?exible. However, even the best-performing software-only fault tolerance techniques have signi?cant performance cost. The overhead of prior work comes from doubled register usage, frequent inter-core communication, or barrier synchronizations. These factors prevent prior techniques from being adopted widely. To address these problems, this dissertation proposes a software-only decoupled program execution framework for fault tolerance. A compiler automatically transforms a program into its corresponding redundant execution version. Only the values that escape the scope of replication may affect the externally behavior of the program and therefore need to be veri?ed for correctness. At program runtime, the program speculates that transient fault detection code never detects a fault, thus allowing decoupled execution of program code, transient fault detection, I/O operations and system calls. A comprehensive misspeculation detection and recovery framework is also described for programs to detect a transient fault and recover from it with low runtime cost. The prototype of this framework was implemented as a set of automatic compiler transformations and evaluated on a commodity multi-core system. The evaluation demonstrated that with this framework, transient fault tolerance can achieve best-in-class performance, high fault coverage, and fast recovery with no hardware module involved.

1 0

Colloquium Speaker, Thomas Anderson, Mon. March 28
by Nicole E. Wagenblast 25 Mar '11

25 Mar '11

Towards a Highly Available Internet Thomas Anderson, University of Washington Monday March 28, 4:30pm Computer Science 105 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.

1 1

Colloquium Speaker- Ruslan Salakhutdinov Thurs March 23
by Nicole E. Wagenblast 22 Mar '11

22 Mar '11

Learning Hierarchical Generative Models Ruslan Salakhutdinov, Massachusetts Institute of Technology Thursday, March 23, 4:30pm Computer Science 105 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.

2 3

Colloquium Speaker Abhinav Gupta March 23
by Nicole E. Wagenblast 21 Mar '11

21 Mar '11

Beyond Naming: Image Understanding via Physical, Functional and Causal Relationships Abhinav Gupta, Carnegie Mellon University Wednesday, March 23, 4:30pm Computer Science 105 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.

1 1

Colloquium speaker- Can Alkan Tues March 22
by Nicole E. Wagenblast 21 Mar '11

21 Mar '11

Next generation sequence characterization of complex genome structural variation Can Alkan, University of Washington Tuesday, March 22, 4:30pm Computer Science 105 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 data sets. 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.

1 1

M Hardt preFPO
by Melissa Lawson 18 Mar '11

18 Mar '11

Moritz Hardt will present his preFPO on Thursday March 24 at 10:30 AM in Room 402. The members of his committee are; Boaz Barak (advisor); Sanjeev Arora and Rocco Servedio (Columbia), readers; Moses Charikar and Rob Schapire, nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------------------------- Algorithmic techniques for privacy-preserving data analysis We address the problem of privacy-preserving analysis of sensitive data. Specifically we are interested in algorithms that satisfy the rigorous privacy standard called differential privacy. In the most basic setting of differential privacy we wish to respond to a number of statistical queries on a data set posed by an (untrusted) data analyst. As differential privacy forces us to give noisy answers, the basic goal is to maximize the accuracy with which we answer each query while maintaining differential privacy. Our results are the following: - We first relate this problem to certain well-studied questions in high-dimensional geometry. Assuming the truth of a deep conjecture about convex bodies, we design a new differentially private algorithm with optimal accuracy so long as the number of queries is smaller than the size of the data set and the queries are asked all at once. - We next develop a privacy-preserving multiplicative weights framework which we use to give an algorithm in the case where the number of queries may be significantly larger than the size of the data set and the queries may be asked interactively. The accuracy of our algorithm is optimal in its dependence on the database size. - We then focus on a notable special case of statistical queries called Boolean conjunctions (aka contingency tables) that are of particular importance from a statistical point of view. Neither of the aforementioned algorithms has a polynomial runtime in this setting. We give the first polynomial time algorithm for answering all Boolean conjunctions with a non-trivial accuracy guarantee while satisfying differential privacy. Our result is based on a new learning algorithm for submodular functions. This talk is based on joint works with Anupam Gupta, Aaron Roth, Guy Rothblum, Kunal Talwar and Jon Ullman.

1 0

4:30pm Mon Mar 28 talk on highly-available Internet
by Jennifer Rexford 15 Mar '11

15 Mar '11

Department colloquium talk: Speaker: Professor Tom Anderson, U. Washington Title: Towards a Highly-Reliable Internet Date/time: 4:30-5:30pm Monday March 28 Place: CS 105 (small auditorium), with tea 4-4:30pm in the CS tea room Abstract: 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.

1 0

Colloquium Speaker Adam Chlipala Tues March 8
by Nicole E. Wagenblast 07 Mar '11

07 Mar '11

Formal Verification of Software Infrastructure: From Science to Engineering Adam Chlipala, Harvard Tuesday, March 8, 4:30pm Computer Science 105 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 U! r/Web.

1 1

Colloquium Speaker, Sepandar Kamvar, Wed. 3/9, 4:30pm
by Nicole E. Wagenblast 07 Mar '11

07 Mar '11

Search and the Social Web: Organizing the World's People and Making them Accessible and Useful Sepandar Kamvar, Stanford University Wednesday, March 9, 4:30pm Computer Science 105 In the past few years, we have seen a tremendous growth in public human communication and self-expression, through blogs, microblogs, and social networks. In addition, we are beginning to see the emergence of a social technology stack on the web, where profile and relationship information gathered by some applications can be used by other applications. This technology shift, and the cultural shift that has accompanied it, offers a great opportunity for computer scientists, artists, and sociologists to study (and organize) people at scale. In this talk I will discuss how the changing web suggests new paradigms for search and discovery. I will discuss some recent projects that use web search to study human nature, and human nature to improve web search. I will describe the underlying principles behind these projects and suggest how they might inform future work in search, data mining, and social computing. Sep Kamvar is a consulting professor of Computational and Mathematical Engineering at Stanford University. His research focuses on social computing and information retrieval. From 2003 to 2007, Sep was the head of personalization at Google. Prior to Google, he was founder and CEO of Kaltix, a personalized search company that was acquired by Google in 2003. Sep is the author of two books and over 40 technical publications and patents in the fields of search and social computing. His artwork is in the permanent collections of the Museum of Modern Art in New York and the Museum of Fine Arts in Houston, and has been exhibited in a number of other museums, including the Victoria and Albert Musem in London and the National Museum of Contemporary Art in Athens. He holds a Ph.D. in Scientific Computing and Computational Mathematics from Stanford University, and an A.B. in Chemistry from Princeton University.

1 0

colloquium speaker Maneesh Agrawala Wed. March 2
by Nicole E. Wagenblast 28 Feb '11

28 Feb '11

Designing Maps to Help People Maneesh Agrawala, Berkeley Wednesday, March 2, 4:30pm Computer Science 105 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.

1 1