March 2012 - talks - lists.cs.princeton.edu

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