- 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

8pm tonight: What Does It Mean To Be Literate in the Age of Google?
by Adam Finkelstein 28 Feb '12

28 Feb '12

This public lecture may be of interest: http://lectures.princeton.edu/2012/daniel-m-russell/ What Does It Mean To Be Literate in the Age of Google? Daniel M. Russell Über Tech Lead for Search Quality and User Happiness, Google February 28, 2012 Louis Clark Vanuxem Lecture What does it mean to be literate at a time when you can search over billions of texts in less than 300 milliseconds? Although you might think that “literacy” is one of the great constants that transcends the ages, the skills of a literate person have changed substantially over time as texts and technology allow for new kinds of reading and understanding. Knowing how to read is just the beginning of it—knowing how to frame a question, pose a query, how to interpret the texts that you find, how to organize and use the information you discover, how to understand your metacognition—these are all critical parts of being literate as well. In this talk Russell review what literacy is today, in the age of Google, and show how some very surprising and unexpected skills will turn out to be critical in the years ahead. Daniel M. Russell is the Über Tech Lead for Search Quality and User Happiness for Google where he studies how people search for and organize information. He earned his PhD in computer science at the University of Rochester (NY), specializing in artificial intelligence until he realized that magnifying and understanding human intelligence was his real passion. Twenty years ago he foreswore AI in favor of HI, and enjoys teaching, learning, running and music, preferably all in one day. He has worked at Xerox PARC before it was PARC.com, was in the Advanced Technology Group at Apple where he wrote the first 100 web pages for www.Apple.com using SimpleText. He has also worked at IBM as a senior research scientist, and briefly at a startup that developed tablet computers a few years before the iPad.

1 0

Colloquium speaker Alekh Agarwal Tuesday Feb 28 4:30pm
by Nicole E. Wagenblast 27 Feb '12

27 Feb '12

Computation meet Statistics: Trade-offs and fundamental limits Alekh Agarwal , University of California, Berkeley Tuesday, February 28, 2012 , 4:30 PM Computer Science Small Auditorium (Room 105) The past decade has seen the emergence of datasets of an unprecedented scale, with both large sample sizes and dimensionality. Massive data sets arise in various domains, among them computer vision, natural language processing, computational biology, social networks analysis and recommendation systems, to name a few. In many such problems, the bottleneck is not just the number of data samples, but also the computational resources available to process the data. Thus, a fundamental goal in these problems is to characterize how estimation error behaves as a function of the sample size, number of parameters, and the computational budget available. In this talk, I present two research threads that provide complementary lines of attack on this broader research agenda: lower bounds for statistical estimation with computational constraints, and (ii) distributed algorithms for statistical inference. The first characterizes fundamental limits in a uniform sense over all methods, whereas the latter provides explicit algorithms that exploits the interaction of computational and statistical considerations in a distributed computing environment. [Joint work with John Duchi, Pradeep Ravikumar, Peter Bartlett and Martin Wainwright] Alekh Agarwal is a fifth year PhD student at UC Berkeley, jointly advised by Peter Bartlett and Martin Wainwright. Alekh has received PhD fellowships from Microsoft Research and Google. His main research interests are in the areas of machine learning, convex optimization, high-dimensional statistics, distributed machine learning and understanding the computational trade-offs in machine learning problems.

1 1

4:30pm Thu Mar 1 talk by Prateek Mittal in E-Quad B205
by Jennifer Rexford 24 Feb '12

24 Feb '12

> > > Speaker: > Prateek Mittal, UIUC > Title: > Trustworthy Communications Using Social Networks > Day: > Thursday, March 1, 2012 > Time: > 4:30 pm > Room: > B205, E-Quad > > Abstract: > Internet systems and applications are shifting towards a participatory paradigm, where users contribute content and resources. Popular examples include reputation systems such as Yelp, peer-to-peer networks, Web 2.0 applications like Wikipedia, and online forums such as Slashdot. These applications, however, struggle with the concepts of identity and trust, as it is easy to create a large number of pseudonyms (called Sybils) that join the system and disrupt its functionality. In this talk, I will outline two mechanisms for defending against the Sybil attack. A common theme in these mechanisms is the use of social network trust relationships to validate user identities. Such an approach forces the adversary to inﬁltrate users’ trusted social circles, presenting a signiﬁcant barrier for attack. > > First, I will present SybilInfer, an algorithm for labeling nodes in a social network as honest users or Sybils controlled by an adversary. SybilInfer uses a combination of Bayesian inference and Monte-Carlo techniques to perform a global analysis of the entire social graph to isolate attackers. Second, I will present X-Vine, a mechanism that enables users in a social network to efficiently communicate with each other, while resisting Sybil attacks. X-Vine is scalable, preserves the privacy of users’ social network contacts, and provides a basis for pseudonymous communication. Finally, I will conclude by highlighting the potential for leveraging social networks in the design of trustworthy communication systems that improve user security and privacy. > > Bio: > Prateek Mittal is a Ph.D. Candidate in Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign. His research in security and privacy focuses on computer networks and distributed systems, with an emphasis on social networks and Internet protocols. He is also interested in applications of network modeling and analysis techniques to interdisciplinary settings, especially cancer genomics. He received the M.E. Van Valkenburg graduate research award for outstanding doctoral research, the Rambus Computer Engineering fellowship, and the ACM CCS 2008 outstanding paper award. He earned his M.S. in Electrical and Computer Engineering at the University of Illinois at Urbana-Champaign and a B.Tech. in Computer Science and Engineering at the Indian Institute of Technology, Guwahati. > > Host: Ruby Lee > > > > > > > > >

1 0

S Gerrish preFPO
by Melissa M. Lawson 23 Feb '12

23 Feb '12

Sean Gerrish will present his preFPO on Wednesday February 29 at 2:30PM in Room 402. The members of his committee are: David Blei, advisor; Rob Schapire and Hanna Wallach (UMass), readers; Kosuke Imai (POL) and Matthew Salganik (SOC), nonreaders. Everyone is invited to attend his talk. His abstract follows below. --------------------------- Title: Patterns of influence and decision-making in politics and foreign relations The past several decades have seen an explosion of digitized information in fields such as political science. In this period, a variety of statistical tools have been developed to better understand patterns in these records by incorporating information such as records of behavior and the text of documents. In this talk, I will present several recent statistical models for discovering patterns in digital records in the fields of politics, bibliometrics, and international relations. These models, which emphasize topic modeling, will link legislative text to voting patterns, written judges' opinions to citations of these opinions, and the text of newspaper articles to countries' international relations. I will also describe details of approximate posterior inference for these models, and will briefly touch upon advances in such methods. This talk includes ongoing work.

1 0