- talks - lists.cs.princeton.edu

A Bell preFPO
by Melissa M. Lawson 28 Feb '13

28 Feb '13

Ana Bell will present her preFPO on Friday March 1 (this Friday) at 10AM in room 302 (note room). The members of her committee are: Olga Troyanskaya, advisor; Mona Singh and Andrea LaPaugh, readers; Kai Li and Tom Funkhouser, nonreaders. Everyone is invited to attend her talk. Her abstract follows below. ----- Original Message ----- Title and Abstract: Integrating Genomic Data to Build Mechanistic Networks for Genes and Small Molecules The recent increase in interest in mining biological data has spurred the aggregation of genomic data from various model organisms into numerous databases. We want to integrate the data available for one of the more well studied organisms, saccharomyces cerevisiae (yeast), and to build mechanistic networks that present interactions between proteins and compounds (small molecules) so that we can accurately predict drug targets. To that end, we apply machine learning algorithms to the data to create the interaction network; a graph where nodes represent proteins or molecules and edges between nodes represent the probability that two nodes interact. Our two step integration process, where we first predict protein-protein interaction networks for various interaction types and then use these networks to predict protein-compound interaction networks, will provide detailed insight into how pathway level knowledge can be leveraged to predict small molecule level interactions. Recent years have also seen an explosion in plant genomics, as the difficulties inherent in sequencing and functionally analyzing these biologically and economically significant organisms have been overcome. Arabidopsis thaliana, a versatile model organism, represents an opportunity to evaluate the predictive power of biological network inference for plant functional genomics. We provide a compendium of functional relationship networks for A. thaliana leveraging data integration based on over 60 microarray, physical and genetic interaction, and literature curation datasets. These include tissue, biological process, and development stage specific networks, each predicting relationships specific to an individual biological context. These biological networks enable the rapid investigation of uncharacterized genes in specific tissues and developmental stages of interest and summarize a very large collection of A. thaliana data for biological examination. We found validation in the literature for many of our predicted networks, including those involved in disease resistance, root hair patterning, and auxin homeostasis.

1 1

Colloquium Speaker Ankur Moitra Wed Feb 27- 4:30pm
by Nicole E. Wagenblast 27 Feb '13

27 Feb '13

New Algorithms for Nonnegative Matrix Factorization and Beyond Ankur Moitra , Institute for Advanced Studies Wednesday, Februar y 27, 2013, 4:30pm Computer Science 105 Machine learning is a vibrant field with many rich techniques. However, these approaches are often heuristic: we cannot prove good bounds on either their performance or their running time except in limited settings. This talk will focus on designing algorithms whose performance can be analyzed rigorously. As an example of this project, I will describe my work on the nonnegative matrix factorization problem, which has important applications throughout machine learning (and theory). As is often the case, this problem is NP-hard when considered in full generality. However, we introduce a sub-case called separable nonnegative matrix factorization that we believe is the right notion in various contexts. We give a polynomial time algorithm for this problem, and leverage this algorithm to efficiently learn the topics in a Latent Dirichlet Allocation model (and beyond). This is an auspicious example where theory can lead to inherently new algorithms that have highly-practical performance on real data sets. I will also briefly describe some of my other work on learning, including mixtures of Gaussians and robust linear regression, as well as promising directions for future work. Ankur Moitra is an NSF CI Fellow at the Institute for Advanced Study, and also a senior postdoc in the computer science department at Princeton University. He completed his PhD and MS at MIT in 2011 and 2009 respectively, where he was advised by Tom Leighton. He received a George M. Sprowls Award (best thesis) and a William A. Martin Award (best thesis) for his doctoral and master's dissertations. He has worked in numerous areas of algorithms, including approximation algorithms, metric embeddings, combinatorics and smoothed analysis, but lately has been working at the intersection of algorithms and learning.

1 2

Colloquium Speaker John Paisley Mon Feb 25, 4:30pm
by Nicole E. Wagenblast 25 Feb '13

25 Feb '13

Bayesian Nonparametric Models and "Big Data" John Paisley , University of California, Berkeley Monday, February 25, 2013, 4:30pm Computer Science Small Auditorium, Room 105 Bayesian nonparametrics is an area in machine learning in which models grow in size and complexity as data accrue. As such, they they are particularly relevant to the world of "Big Data", where it may be difficult or even counterproductive to fix the number of parameters a priori. A stumbling block for Bayesian nonparametrics has been that their algorithms for posterior inference generally show poor scalability. In this talk, we tackle this issue in the domain of large-scale text collections. Our model is a novel tree-structured model in which documents are represented by collections of paths in an infinite-dimensional tree. We develop a general and efficient variational inference strategy for learning such models based on stochastic optimization, and show that with this combination of modeling and inference approach, we are able to learn high-quality models using millions of documents. John Paisley received the B.S.E. (2004), M.S. (2007) and Ph.D. (2010) in Electrical & Computer Engineering from Duke University, where his advisor was Lawrence Carin. He was a postdoctoral researcher with David Blei in the Computer Science Department at Princeton University, and currently with Michael Jordan in the Department of EECS at UC Berkeley. He works on developing Bayesian models for machine learning applications, particularly for dictionary learning and topic modeling.

1 2

C Park preFPO
by Melissa M. Lawson 21 Feb '13

21 Feb '13

Chris Park will present his preFPO on Tuesday February 26 at 1:30PM in Room 402. The members of his committee are: Olga Troyanskaya, advisor; Mona Singh and Kai Li, readers; Rob Schapire and Moses Charikar, nonreaders. Everyone is invited to attend his talk. His abstract follows below. ---------------------------------------------------------------- Title: Inferring gene function and heterogeneous gene networks from genomic data Abstract With the advancement of quantitative biology, there has been a dramatic increase in functional genomic data. Using these genomic datasets which includes protein-protein interaction, gene expression, localization, and gene knockout studies has enabled researchers to construct functional gene networks. In functional gene networks, each edge represents the probabilistic support for a functional relationship between two genes. However in practice, the goal of biology is to understand further depth of the function and relationship between genes, beyond the abstract notion of a functional relation. In this work, we expand the depth and breadth of functional gene networks. First, we demonstrate that functional gene networks can improve the transfer of gene annotations between organisms to allow prediction algorithms to identify additional genes participating in biological processes that are not already well studied. We apply our novel functional knowledge transfer method to accurately predict novel gene functions across six diverse organisms. Second, biomolecular pathways are built from diverse types of pairwise interactions, ranging from physical protein-protein interactions and modifications to indirect regulatory relationships. One goal of systems biology is to bridge three aspects of this complexity: the growing body of high-throughput data assaying these interactions; the specific interactions in which individual genes participate; and the genome-wide patterns of interactions in a system of interest. Here, we describe methodology for predicting specific types of biomolecular interactions, beyond functional relationship, using high-throughput genomic data in both yeast and human. Ultimately, our work provides further insight into the genetic wiring of the cell enabled by large-scale machine learning with genome-wide biological data.

1 0

reminder: talk now (3pm) on flow-cut gaps and network coding in room 402
by Jennifer Rexford 05 Feb '13

05 Feb '13

Speaker: Anna Blasiak, Cornell Title: Flow-Cut Gaps and Network Coding Date/time: 3-4pm on Tuesday February 5 Place: 402 in the CS building Abstract: The classic max-flow min-cut theorem states that in a network with one source and one sink, the amount of information that can be sent from the source to the sink is equal to the minimum capacity of a set of edges separating the source from the sink. This equivalence allows for efficient computation of both parameters. Modifying traffic demands, constraints, and optimization functions yields many variations of the max-flow problem. In all of these variations there is a corresponding cut minimization problem whose optimal value serves as an upper bound on the max-flow. But unlike the single source-sink version, the cut upper bound is rarely equal to the max-flow. The flow-cut gap, the worst possible ratio between the max-flow rate and the cut upper bound, is an important area of study for developing approximation algorithms and gaining a better understanding of network flow. Related to the max-flow problem is the network coding rate, the maximum transmission rate of information in networks whose nodes can perform nontrivial encoding and decoding operations on incoming messages. The network coding rate is always as big as the max-flow rate and can be much larger. A spectacular result of network coding theory is that in the multicast problem, a setting with a large flow-cut gap, the coding rate is always equal to the cut bound. This talk considers the relations between the flow rate, coding rate, and cut bounds for multicommodity flow problems. I present new coding-cut gaps, the worst-case ratio between the coding rate and cut upper bound. Further, I show that there exist paradigms apart from multicast in which coding can bridge the flow-cut gap. Specifically, in the network that provides the largest known separation (Saks et al.) between the maximum multicommodity flow and multicut, the coding rate is equal to the multicut. This is joint work with Robert Kleinberg (Cornell University) and Eyal Lubetzky (Microsoft Research Redmond).

1 0

3pm Tue Feb 5 talk on flow-cut gaps *rescheduled: was originally Thu Feb 7*
by Jennifer Rexford 02 Feb '13

02 Feb '13

Speaker: Anna Blasiak, Cornell Title: Flow-Cut Gaps and Network Coding Date/time: 3-4pm on Tuesday February 5 Place: 402 in the CS building Abstract: The classic max-flow min-cut theorem states that in a network with one source and one sink, the amount of information that can be sent from the source to the sink is equal to the minimum capacity of a set of edges separating the source from the sink. This equivalence allows for efficient computation of both parameters. Modifying traffic demands, constraints, and optimization functions yields many variations of the max-flow problem. In all of these variations there is a corresponding cut minimization problem whose optimal value serves as an upper bound on the max-flow. But unlike the single source-sink version, the cut upper bound is rarely equal to the max-flow. The flow-cut gap, the worst possible ratio between the max-flow rate and the cut upper bound, is an important area of study for developing approximation algorithms and gaining a better understanding of network flow. Related to the max-flow problem is the network coding rate, the maximum transmission rate of informati! on in networks whose nodes can perform nontrivial encoding and decoding operations on incoming messages. The network coding rate is always as big as the max-flow rate and can be much larger. A spectacular result of network coding theory is that in the multicast problem, a setting with a large flow-cut gap, the coding rate is always equal to the cut bound. This talk considers the relations between the flow rate, coding rate, and cut bounds for multicommodity flow problems. I present new coding-cut gaps, the worst-case ratio between the coding rate and cut upper bound. Further, I show that there exist paradigms apart from multicast in which coding can bridge the flow-cut gap. Specifically, in the network that provides the largest known separation (Saks et al.) between the maximum multicommodity flow and multicut, the coding rate is equal to the multicut. This is joint work with Robert Kleinberg (Cornell University) and Eyal Lubetzky (Microsoft Research Redmond).

1 0

Graham Cormode visiting
by Ariel Rabkin 30 Jan '13

30 Jan '13

Hi all. Here's another in our series of data and database talks. Talk will be on Weds Jan 30, Room 302 at noon. NOTE THAT THERE WILL NOT BE A REMINDER THE DAY-OF, BECAUSE MAILING LISTS WILL BE DOWN DUE TO MIGRATION!!! Let me know if you want to meet with the speaker; should be of interest to both theory and systems people. Talk: Small Summaries for Big Data In dealing with big data, we often need to look at a small summary to get the big picture. Over recent years, many new techniques have been developed which allow important properties of large distributions to be extracted from compact and easy-to-build summaries. In this talk, I'll highlight some examples of different types of summarization: sampling, sketching, and special-purpose. Then I'll outline the road ahead for further development of such summaries. Graham Cormode is a Principal Member of Technical Staff in the Database Management Group at AT&T Shannon Laboratories in New Jersey. Previously, he was a researcher at Bell Labs, after postdoctoral study at the DIMACS center in Rutgers University from 2002-2004. His PhD was granted by the University of Warwick in 2002. His work considers aspects of managing and working with large amounts of data, with particular emphasis on privacy and anonymization, and large scale analytics. --Ari

2 1

11am Thu Feb 7 talk on flow-cut gaps and network coding
by Jennifer Rexford 21 Jan '13

21 Jan '13

Speaker: Anna Blasiak, Cornell Title: Flow-Cut Gaps and Network Coding Date/time: 11am-noon on Thursday February 7 Place: 402 in the CS building Abstract: The classic max-flow min-cut theorem states that in a network with one source and one sink, the amount of information that can be sent from the source to the sink is equal to the minimum capacity of a set of edges separating the source from the sink. This equivalence allows for efficient computation of both parameters. Modifying traffic demands, constraints, and optimization functions yields many variations of the max-flow problem. In all of these variations there is a corresponding cut minimization problem whose optimal value serves as an upper bound on the max-flow. But unlike the single source-sink version, the cut upper bound is rarely equal to the max-flow. The flow-cut gap, the worst possible ratio between the max-flow rate and the cut upper bound, is an important area of study for developing approximation algorithms and gaining a better understanding of network flow. Related to the max-flow problem is the network coding rate, the maximum transmission rate of information in networks whose nodes can perform nontrivial encoding and decoding operations on incoming messages. The network coding rate is always as big as the max-flow rate and can be much larger. A spectacular result of network coding theory is that in the multicast problem, a setting with a large flow-cut gap, the coding rate is always equal to the cut bound. This talk considers the relations between the flow rate, coding rate, and cut bounds for multicommodity flow problems. I present new coding-cut gaps, the worst-case ratio between the coding rate and cut upper bound. Further, I show that there exist paradigms apart from multicast in which coding can bridge the flow-cut gap. Specifically, in the network that provides the largest known separation (Saks et al.) between the maximum multicommodity flow and multicut, the coding rate is equal to the multicut. This is joint work with Robert Kleinberg (Cornell University) and Eyal Lubetzky (Microsoft Research Redmond).

1 0

A Blankstein general exam
by Melissa M. Lawson 17 Jan '13

17 Jan '13

Aaron Blankstein will present his research seminar/general exam on Thursday January 24 at Noon in Room 402. The members of his committee are: Michael Freedman (advisor), Ed Felten, and Vivek Pai. Everyone is invited to attend his talk, and those faculty wishing to remain for the oral exam following are welcome to do so. His abstract and reading list follow below. ----- Original Message ----- Abstract: In many client-facing applications, a vulnerability in any portion can compromise the entire application. In this talk, I describe the design and implementation of Passe, a web framework that provides integrity and conﬁdentiality guarantees for existing applications. Passe automatically splits (previously single-process) web applications into sandboxed processes, and then limits the types of queries each component can make to shared storage. While previous approaches like Decentralized Information Flow Control sought to provide security guarantees by explicitly labeling and tracking data, Passe provides similar guarantees by instead enforcing integrity constraints on database queries, even when they originate from compromised components. Further, rather than requiring developers to specify such constraints explicitly, Passe infers these constraints during a testing phase, in which it assumes that the “proper” execution of database queries is reading and writing data appropriately. Such policy inference allows Passe to execute unmodiﬁed applications without explicit policies. I present a prototype of Passe which acts as a drop-in replacement for the Django web framework. By running seven unmodiﬁed, off-the shelf applications in Passe, I demonstrate its ability to provide strong security guarantees with reasonable performance. Reading List "Principles of Computer System Design" - Saltzer and Kaashoek "The KeyKOS Nanokernel Architecture" A. Bomberger, A. Frantz, W. Frantz, A. Hardy, N. Hardy, C. Landau, and J. Shapiro. "Complete, Safe Information Flow with Decentralized Labels" A. Myers and B. Liskov. "Hails: Protecting data privacy in untrusted web applications." Daniel B. Giffin, Amit Levy, Deian Stefan, David Terei, David Mazières, John Mitchell, and Alejandro Russo. “The protection of information in computer systems,” J. H. Saltzer and M. D. Schroeder, "Information Flow Control for Standard OS Abstractions" (Flume) Max Krohn, Alexander Yip, Micah Brodsky, Natan Cliffer, M. Frans Kaashoek, Eddie Kohler, Robert Morris "Making information flow explicit in HiStar. " Nickolai Zeldovich, Silas Boyd-Wickizer, Eddie Kohler, and David Mazières. “Bugs as deviant behavior: a general approach to inferring errors in systems code" D. Engler, D. Y. Chen, S. Hallem, A. Chou, and B. Chelf “All you ever wanted to know about dynamic taint analysis and forward symbolic execution (but might have been afraid to ask),” E. J. Schwartz, T. Avgerinos, and D. Brumley “Building secure high-performance web services with OKWS" - Max Krohn

1 0

I Davey generals
by Melissa M. Lawson 16 Jan '13

16 Jan '13

Ian Davey will be presenting his research seminar/general exam (talk only) on Wednesday January 23 at 2PM in Sherrerd 306 (Note Location!). The members of his committee are: Ed Felten (advisor), Michael Freedman, and Zeev Dvir. Everyone is invited to attend his talk. ----- Original Message ----- Collective Security for Resistance to Mass Harvesting of Publicly-Available Information As internet users produce and share increasing amounts of content, some new privacy concerns appear. In particular, various entities who have no personal interest in any particular author will nonetheless crawl the internet and harvest any public data they can find. While users may be perfectly happy to share thoughts, photos, video, and contact information with other human users (including complete strangers), they may not wish for the data to be grabbed automatically at scale and used for targeted advertising, spam, search indexing and archiving, etc. Ultimately this becomes an instance of the key distribution problem --- while normal encryption may appear at first the obvious solution, in this case we cannot expect the author to have an existing relationship with his/her audience, and thus there is not necessarily an out-of-band channel through which to exchange key data. However, also in this case, while each member of the desired audience has a limit to the amount of content he/she wishes to view, the adversary has no such limit and wishes to scrape everything. We can exploit this property to find a solution. In this talk we formally define a notion of ``collective security,'' which allows for the recovery of individual pieces of data but provides resistance to mass harvesting of the entire corpus of content. We then propose methods which use weak symmetric ciphers and/or hyperencryption to fill this requirement and prove a theoretical upper bound on its effectiveness. We also propose a system of ``shortcuts'' in case a (possibly one-way) channel for key exchange exists between an author and a viewer. We then present experimental results, explore an economy where barriers to mass information harvesting exist, and describe a browser extension which implements some of our techniques.

1 0