- talks - lists.cs.princeton.edu

Colloquium Speaker, Ira Kemelmacher-Shlizerman, Wed March 14th, 4:30pm
by Nicole E. Wagenblast 12 Mar '12

12 Mar '12

Modeling People from Billions of Photos Ira Kemelmacher-Shlizerman , University of Washington Wednesday, March 14th, 2012, 4:30pm Computer Science Small Auditorium (Room 105) Internet and personal photo collections now add up to over a trillion photos, with people being in most of them. The availability of so many photos presents a unique opportunity to model virtually the whole human population. Modeling humans is key to understanding how people interact with the environment, and to future human machine interfaces. In this talk, I will describe our work on 3D shape and motion estimation of a human face from large photo collections, as well as novel techniques for browsing those collections. This represents an exciting breakthrough towards modeling and visualizing any person just from their available photos. Part of this work is now included in Google’s Picasa. Ira Kemelmacher-Shlizerman is a Postdoctoral researcher in the Department of Computer Science and Engineering at the University of Washington. She received her Ph.D in computer science and applied mathematics at the Weizmann Institute of Science in 2009. Dr. Kemelmacher-Shlizerman works in computer vision and graphics, with a particular interest in developing computational tools for modeling people from Internet and personal photo collections. Ira's recent research was covered by stories in New Scientist, CBS, Discovery News and others. She was also consulting for Google.

1 0

Colloquium Speaker Domagoj Babic Mon March 12th 4:30pm
by Nicole E. Wagenblast 08 Mar '12

08 Mar '12

Software Testing and Verification with Grammatical Inference Domagoj Babic , University of California, Berkeley Recent progress in automated deductive reasoning techniques has triggered a small scientific revolution in automated software testing, verification, and security. Indeed, it is becoming increasingly difficult to find new automated software analysis papers that do not use or assume existence of propositional satisfiability and satisfiability-modulo theories solvers. In this talk, I will discuss the first results of my efforts to answer a simple question: What kind of automated reasoning will trigger the next scientific revolution in automated software analysis? As a potential candidate, I will present grammatical inference (GI), a class of techniques for learning formal languages. By inductively generalizing from examples, GI techniques nicely complement the capabilities of existing (deductive) approaches. Furthermore, the inferred grammars (or automata) are themselves analyzable objects, which can be used as approximations or abstractions of the behavior of the analyzed program. In this talk, I'll analyze several open problems, namely (1) test generation for programs whose inputs have to adhere to complex grammars, and (2) automated verification of web sanitizers, and offer some solutions. The common trait of the above mentioned problems is that they require exact or approximate understanding of the relation between program's input and output. I'll explain how GI techniques can infer such relations and serve as a basis for inventing new powerful software analyses. In particular, I'll show that GI-based automated testing can find six times more vulnerabilities than the state-of-the-art methods, increasing code coverage by up to 58%. The novel symbolic learning technique that I'll present learns input-output relations of web sanitizers (for subsequent verification) in seconds, while construction of the same relations used to take several hours of a human expert's time in the past. Domagoj Babic received his Dipl.Ing. in Electrical Engineering and M.Sc. in Computer Science from the Zagreb University (Faculty of Electrical Engineering and Computing) in 2001 and 2003. He received his Ph.D. in Computer Science in 2008 from the University of British Columbia. After spending a bit more than a year in industry, he joined UC Berkeley, as a research scientist. Domagoj's research focuses on various aspects of software analysis (software verification, testing, and security), decision procedures, grammatical inference, and applied formal methods in general. He is a recipient of the Canada's NSERC PDF Research Fellowship (2010-2012), Microsoft Graduate Research Fellowship (2005-2007), Fulbright Fellowship (declined to attend UBC), and several awards at international programming competitions (1st place at the 2007 Satisfiability Modulo Theories competition in the bit-vector arithmetic category and 3rd place at the 2005 Satisfiability Testing competition in the satisfiable-crafted instances category). For more, see: http://www.domagoj.info/

1 0

4:30pm Thu Mar 8 talk on sparse recovery over networks in B205
by Jennifer Rexford 08 Mar '12

08 Mar '12

DEPARTMENT OF ELECTRICAL ENGINEERING SEMINAR SERIES Speaker: A. Kevin Tang, Cornell University Title: Sparse Recovery over Networks Date/time: 4:30pm Thursday, March 8th Room: E-Quad B-205 Host: Mung Chiang ABSTRACT: Given that large scale networks such as the Internet and power grids have become ever more crucial for our society, it is critical to keep monitoring states of such networks to avoid possible system failure and to optimize performance. The scale and complexity of such systems raise the need to quickly infer component characteristics from a relatively small number of indirect aggregate measurements. Motivated by tomography problems in information networks, we first discuss sparse recovery with graph constraints in the sense that we can take additive measurements over nodes only if they induce a connected subgraph. We provide explicit measurement constructions for several special graphs including line, 2-D grid and tree. A general measurement construction algorithm is also proposed and evaluated. For any given graph G with n nodes, we derive order optimal upper bounds of the minimum number of measurements needed to recover any k-sparse vector over G. Second, to deal with bad data detection in power grids, an iterative mixed L1 and L2 convex programming is used to estimate the true state by locally linearizing the nonlinear measurements. We give conditions under which the solution of the iterative algorithm converges to the true state. We also numerically evaluate our solution to perform bad data detections in nonlinear electrical power networks problems. Besides their clear applications, both formulations significantly generalize the current compressive sensing framework: from complete graph to arbitrary graph (first part of the talk) and from additive linear measurements to nonlinear measurements (second part of the talk). BIO: A. Kevin Tang received his undergraduate degree in electronics engineering from Tsinghua University, Beijing, China, and his Ph.D. in electrical engineering with a minor in applied and computational mathematics from the California Institute of Technology. He is currently an Assistant Professor in the School of Electrical and Computer Engineering at Cornell, where his research interests focus on control and optimization of various networks, including communication networks, power networks, and on-chip networks. His recent awards include a Michael Tien'72 Excellence in Teaching Award from the college of engineering at Cornell in 2011 and a Young investigator award from the US Air Force's Office of Scientific Research in 2012.

1 0

Ari Rabkin talk starting in 5 minutes, room 302
by Mike Freedman 07 Mar '12

07 Mar '12

Using Static Analysis to Diagnose Misconfigured Open Source Systems Software Ariel Rabkin, University of California, Berkeley Ten years ago, few software developers worked on distributed systems. Today, developers often run code on clusters, relying on large open-source software stacks to manage resources. These systems are challenging to configure and debug. Fortunately, developments in program analysis have given us new tools for managing the complexity of modern software. This talk will show how static analysis can help users configure their systems. I present a technique that builds an explicit table mapping a program's possible error messages to the options that might cause them. As a result, users can get immediate feedback on how to resolve configuration errors. --- Ariel Rabkin is a fifth (and final)-year PhD candidate in the RAD Lab at UC Berkeley, working with Randy Katz. He is formerly from Cornell University, AB 2006, MEng 2007). He is interested in software quality and software intelligibility. He expects to graduate in May 2012. His dissertation is about applying program analysis to system management, including automatically describing program configuration options and diagnosing configuration errors. He is a contributor to several open source projects, including Hadoop, the Chukwa log collection framework, and the JChord program analysis toolset.

1 0

Colloquium speaker, Arvind Narayanan, Thrus. March 8th 4:30pm
by Nicole E. Wagenblast 07 Mar '12

07 Mar '12

Data Privacy Technologies: From Alchemy to an Engineering Discipline Arvind Narayanan , Stanford University Thursday, March 8, 2012 , 4:30 PM Computer Science Small Auditorium (Room 105) Established practices for data privacy focus on simplistic transformations such as the removal of “personally identifiable information.” On the other hand, academia has produced a long line of work on privacy-preserving computation that has yet to be translated into practice. I envision privacy technologies as an engineering discipline grounded in a solid understanding of what technological mechanisms can and cannot do. In this talk I will describe my past, ongoing and planned work towards this goal. The first part of this research program — and the main topic of my doctoral work — has been to demonstrate the inadequacy of the current paradigm by developing reidentification and statistical inference algorithms for various types of “anonymized” data: our preferences, transactions, social relationships, and behavior. The second part is to develop an approach to building systems based on lightweight cryptography, a hybrid of centralized and decentralized architectures, and incorporation of policy-based defenses. I will describe how I have applied these principles to my work on location privacy and behavioral ad targeting. Arvind Narayanan is a post-doctoral computer science researcher at Stanford and a junior affiliate scholar at the Stanford Law School Center for Internet and Society. He completed his Ph.D at UT Austin in 2009. Narayanan studies information privacy and security, and moonlights in policy. His paper on deanonymization of large datasets won the 2008 Privacy Enhancing Technologies award and his 2011 paper on location privacy at NDSS won the distinguished paper award.

1 1

Colloquium Speaker Ben Langmead Tuesday March 6th 4pm
by Nicole E. Wagenblast 06 Mar '12

06 Mar '12

Computational approaches for the DNA sequencing data deluge Ben Langmead , University of Maryland College Park Tuesday, March 6, 2012, 4:30pm Computer Science Small Auditorium (Room 105) Second-generation DNA sequencers are improving rapidly and are now capable of sequencing hundreds of billions of nucleotides of data in about a week for a few thousand dollars. Consequently, sequencing has become a common tool in many fields of life science. But with these developments comes a problem: growth in per-sequencer throughput is drastically outpacing growth in computer speed. As the throughput gap widens over time, the crucial research bottlenecks are increasingly computational: computing, storage, labor, power. these lines, I will discuss collaborative scientific projects in epigenetics and gene expression profiling for which I provided novel computational methods in areas such as read alignment, text indexing, and data-intensive computing. I will also discuss a new set of methods for very time- and space-efficient alignment of sequencing reads: Bowtie and Bowtie 2. These tools build on the insight that the Burrows-Wheeler Transform and the FM Index, previously used for data compression and exact string matching, can be extended to facilitate fast and memory-efficient alignment of DNA sequences to long reference genomes such as the human genome. Ben Langmead is a Research Associate in the Department of Biostatistics at the Johns Hopkins Bloomberg School of Public Health. He completed his Ph.D. in Computer Science in February 2012 at University of Maryland, advised by Steven L. Salzberg. His research addresses problems at the intersection of computer science and genomics, and he is the author of several open source software tools for analysis of high-throughput genomics data, including Bowtie, Bowtie 2, Crossbow and Myrna. His paper describing Bowtie won the Genome Biology award for outstanding paper published in 2009. At Johns Hopkins, he collaborates with biostatisticians, biomedical engineers, biologists, and other computer scientists to develop methods for analyzing second-generation DNA sequencing data.

1 1

S Sen preFPO
by Melissa M. Lawson 06 Mar '12

06 Mar '12

Sid Sen will present his preFPO on Thursday March 8 at 11AM in Room 402. The members of his committee are: Bob Tarjan, advisor, reader; Michael Freedman, advisor, reader; Jen Rexford, reader; Vivek Pai and Bob Sedgewick, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------------------- Title: New Data Structures and Algorithms for Highly-Available Distributed Systems Abstract: We design new data structures and algorithms to improve the availability of distributed systems. Our work spans several settings, from individual database servers to large-scale peer-to-peer systems. A unifying approach in our work is to synergize theory and systems until a solution that is both practical and provably good is attained. In database systems, availability suffers when transactions contend for locks on shared index structures. To increase transaction concurrency, many databases such as Berkeley DB avoid rebalancing B-tree indices after deletions, only rebalancing after insertions. But when one company tried this technique with red-black trees, the result was an extended downtime and litigation. Using a novel exponential-potential analysis, we theoretically justify why deletion without rebalancing works in B-trees but fails in red-black trees, and devise a new binary tree called Ravl trees that works. In peer-to-peer systems, the availability of a service depends on unreliable participant machines. These machines fail not just by crashing, but also in arbitrary ways, e.g. due to bugs or malice. To scale such a system securely, we must partition it into smaller groups that remain locally correct despite a dynamic, global adversary. We expose serious practical limitations in the current-best algorithm for this, and devise a new algorithm called Commensal Cuckoo that keeps the system available two orders of magnitude longer. In enterprise desktop and some server cluster settings, availability is often desired in conjunction with energy efficiency. Unfortunately, existing energy-saving solutions require special hardware or virtualization technology that IT departments are unwilling to deploy. To address this, we built GreenUp, a system that allows any machine to act as a proxy for other sleeping machines, ensuring their availability to clients seamlessly. Notably, while optimizing load distribution in GreenUp, we discovered and analyzed a new balls-in-bins process with connections to population genetics and high-dimensional geometry. GreenUp is deployed on over ~1,100 machines within Microsoft. Though often ignored, networking is as critical to the availability of a system as the servers themselves. Beyond connectivity, congestion in the network can render services unavailable by starving traffic, even when sufficient bandwidth exists. We address this problem in datacenter networks through LocalFlow, a flow routing algorithm based on splitting flows. Unlike prior solutions, LocalFlow is switch-local (and hence scalable) and routes optimally. Realizing LocalFlow required a novel theoretical model as well as novel mechanisms for practical deployment on programmable commodity switches.

1 0

S Sevinc preFPO
by Melissa M. Lawson 01 Mar '12

01 Mar '12

Soner Sevinc will present his preFPO on Thursday March 8 at 9AM in Room 402. The members of his committee are: Larry Peterson, advisor; Jennifer Rexford and Andy Bavier, readers; David Walker and Michael Freedman, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------------------------- Discovering and authorizing resources dispersed across autonomous organizations is a challenge for federations as they scale. We introduce a delegation logic for federation to address the problem of authentication and authorization in large scale. A Federation Policy Language (FPL) is used to express this logic, and allows expression of custom security and allocation policies. One distinguishing feature of FPL is that it utilizes a DHT for storage/retrieval of certificates to increase fault-tolerance, efficiency and expressivity in proof constructions. Our contract based discovery and allocation system, CODAL, performs policy-driven peer discovery and collaborative resource discovery/allocation to address two problems: (1) participants in a federation can be unknown, and (2) their resource information and policies can be private. We evaluate our design in PlanetLab, emulating a realistic federation based on PlanetLab usage logs. Results show that our system is capable of discovering and allocating resources in a large scale federation, fulfilling a request from tens of organizations. We also show allocation policies are successfully enforced by our language,and explore run-time characteristics of the FPL proof construction process, and investigate certificate retrieval in terms of time and incurred system load.

1 0

A Vijayaraghavan preFPO
by Melissa M. Lawson 01 Mar '12

01 Mar '12

Aravindan Vijayaraghavan will present his preFPO on Wednesday March 7 at 11AM in Room 302 (note room). The members of his committee are: Moses Charikar, advisor; Sanjeev Arora and Mark Braverman, readers; David Blei and Konstantin Makarychev, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------- Understanding Approximability through Average-case Analysis We study the approximability of fundamental graph optimization problems through approximation algorithms for both realistic average-case and worst-case instances of problems. We study average-case instances to shed new light on approximability in two ways : 1. designing better algorithms for realistic average-case instances. 2. designing new algorithms with better guarantees even in worst-case, and identifying new barriers for further progress. In the first part of the thesis, we study Graph partitioning problems which are ubiquitous in computer science and form a central topic of study. However, constant factor approximations have been elusive. Since real-world instances are unlikely to behave like worst-case instances, a compelling question is : can we design better algorithms for realistic average case instances? We study a semi-random model for graph partitioning problems, that is more general than previously studied random models, and that seems to capture many real-world instances well. We design new O(1) approximation algorithms for classical graph partitioning problems like Balanced Separator, Sparsest cut, Multicut and Small set expansion for these semi-random instances. Our algorithms are based on new SDP-based techniques and work in a wider range of parameters than algorithms for previously studied random and semi-random models. In the second part, we show how insights from algorithms for a natural average-case version are used to obtain new worst-case approximation algorithms for the Densest k-Subgraph problem -- an important yet poorly understood problem in combinatorial optimization. The counting-based algorithms for the average-case version of the problem are translated to algorithms for the worst-case using linear programming hierarchies: this gives an improved n^{1/4} factor approximation. Studying the average-case version also points to a concrete barrier for further progress on approximations for Densest k-subgraph. These results are based on joint works with Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Venkatesan Guruswami, Konstantin Makarychev, Yury Makarychev and Yuan Zhou.

1 0

3:00pm Mon Mar 5: Uday Khedker on Heap Reference Analysis
by Moses S. Charikar 01 Mar '12

01 Mar '12

Speaker: Uday Khedker, IIT Bombay Title: Heap Reference Analysis Using Access Graphs Day: Monday, March 5, 2012 Time: 3:00 pm Room: Room 402, CS building Abstract: Despite significant progress in the theory and practice of program analysis, analyzing properties of heap data has not reached the same level of maturity as the analysis of static and stack data. The spatial and temporal structure of stack and static data is well understood while that of heap data seems arbitrary and is unbounded. We devise bounded representations which summarize properties of the heap data. This summarization is based on the structure of the program which manipulates the heap. The resulting summary representations are certain kinds of graphs called access graphs. The boundedness of these representations and the monotonicity of the operations to manipulate them make it possible to compute them through data flow analysis. An important application which benefits from heap reference analysis is garbage collection, where currently liveness is conservatively approximated by reachability from program variables. As a consequence, current garbage collectors leave a lot of garbage uncollected, a fact which has been confirmed by several empirical studies. We propose the first ever end-to-end static analysis to distinguish live objects from reachable objects. We use this information to make dead objects unreachable by modifying the program. This application is interesting because it requires discovering data flow information representing complex semantics. In particular, we formulate the following new analyses for heap data: liveness, availability, and anticipability and propose solution methods for them. Together, they cover various combinations of directions of analysis (i.e. forward and backward) and confluence of information (i.e. union an! d interse ction). Our analysis can also be used for plugging memory leaks in C/C++ languages. Reference: Uday P. Khedker, Amitabha Sanyal, and Amey Karkare. Heap Reference Analysis Using Access Graphs. ACM Transactions on Programming Languages & Systems. 30, 1 (Nov. 2007), 1. DOI=http://doi.acm.org/10.1145/1290520.1290521.

1 0