- talks - lists.cs.princeton.edu

R Manokaran preFPO
by Melissa M. Lawson 26 Mar '12

26 Mar '12

Rajsekar Manokaran will present his preFPO on Wednesday March 28 at 1:30PM in Room 402. The members of his committee are: Sanjeev Arora, advisor; Moses Charikar and Zeev Dvir, readers; Mark Braverman and Bernard Chazelle, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ------------------- Title: Approximability using Mathematical Relaxations A standard approach to coping with the NP-hardness of a combinatorial optimization problem involves designing algorithms that guarantee a solution within a factor p of the optimum (a.k.a an p-approximation algorithm). We study the approximability of various fundamental graph optimization problems using linear programming~(LP) relaxations. In the first part of the thesis, we study simple LP relaxations for Metric Labeling, and a variety of Packing and Covering problems. For all these problems, we show that the relaxation already obtains the best approximation, upto known algorithmic barriers. The novelty here is the generality of the technique: the proof only uses simple "local" properties of the relaxation, oblivious of the actual approximation factor, p, obtained thus. In the second part, we use insights obtained from the above in studying the approximability of a large class of ordering problems, including the Maximum Acyclic Subgraph problem. Here, we show that a trivial algorithm, that outputs a random ordering irrespective of the instance in hand, already achieves the best appromximation factor upto known algorithmic techniques. In the final part, we study implications of "average-case" algorithmic barriers. In particular, we show that the densest-k-subgraph problem is hard to approximate to within any constant factor assuming random k-AND formulas are hard to distinguish from well satisfiable ones. These results are based on joint works with Noga Alon, Sanjeev Arora, Moses Charikar, Venkatesan Guruswami, Johan Hastad, Amit Kumar, Dana Moshkovitz, Joseph Naor, Prasad Raghavendra, Roy Schwartz, Madhur Tulsiani, Nisheeth Vishnoi and Omri Weinstein

1 0

Yun Zhang FPO
by Melissa M. Lawson 23 Mar '12

23 Mar '12

Yun Zhang will present her FPO on Thursday March 29 at 2PM in Room 402. The members of her committee are: David August, advisor; David Walker and Scott Mahlke (Michigan), readers; Doug Clark and Jen Rexford, nonreaders. A copy of her thesis, "Runtime Speculative Software-Only Fault Tolerance", is on display in Room 310. Everyone is invited to attend her talk.

1 0

Colloquium speaker Shyamnath Gollakota, Mon March 26th 4:30pm
by Nicole E. Wagenblast 23 Mar '12

23 Mar '12

Embracing Interference in Wireless Systems Shyamnath Gollakota , Massachusetts Institute of Technology Monday, March 26, 4:30pm Computer Science Small Auditorium (Room 105) The wireless medium is a shared resource. If nearby devices transmit at the same time, the transmitted signals interfere, resulting in a collision. In traditional networks, collisions cause the loss of the transmitted information. For this reason, wireless systems have been designed with the assumption that interference is intrinsically harmful and must be avoided. My research takes an alternate approach: Instead of viewing interference as an inherently counterproductive phenomenon that should to be avoided, I design practical systems that can successfully reconstruct the transmitted information even in the presence of collisions; hence, rendering the interference harmless. Moreover, these new systems can exploit interference constructively to increase throughput and improve security. In the talk, I will present the first WiFi receiver that decodes colliding packets, rendering WiFi interference harmless. I will also show how to inject useful interference that increases network throughput using a system called analog network coding. Then, I will talk about the role of interference in improving security. I will use interference to secure insecure medical implants, and establish secure wireless connections without having users enter passwords or use pre-shared secret keys. Shyamnath Gollakota is a PhD candidate in Electrical Engineering and Computer Science at the Massachusetts Institute of Technology. His research in networking focuses on addressing wireless interference and security. He has been awarded the ACM SIGCOMM 2008 Best paper award for ZigZag decoding, ACM SIGCOMM 2011 Best Paper Award for securing medical implants, and AT&T Applied Security Award for password-free wireless security. His work has appeared in venues like Slashdot, BBC Radio, Forbes, and Network World. He received his masters in Electrical Engineering and Computer Science at MIT, and a bachelors degree in Computer Science and Engineering at IIT Madras.

1 1

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