- talks - lists.cs.princeton.edu

Colloquium Speaker Aaron Turon Thurs Feb 20, 4:30pm
by Nicole E. Wagenblast 19 Feb '14

19 Feb '14

Practical Foundations for Scalable Concurrency Aaron Turon ( Max Planck Institute for Software Systems (MPI-SWS) Thursday, February 20, 4:30pm Computer Science 105 The traditional way to tame concurrency is to disallow it: "critical sections" of code can be protected by locks, preventing interference from concurrent threads, but also cutting down opportunities for parallelism. The past two decades have produced a wealth of data structures that instead tolerate (or even embrace) concurrency for the sake of scaling with available parallelism. But despite the importance of these "scalable" (e.g., lock-free) data structures, many basic questions about them have remained unanswered. My work has focused on several such questions; this talk will cover two of them. First, what are the fundamental abstractions for scalable concurrency? I will present Reagents, the first high-level programming model for building lock-free data structures. Reagents solve a key problem for concurrency libraries: they allow library clients to combine data structure operations while retaining strong scalability and atomicity properties, and without requiring the clients to understand the underlying algorithms. Second, how can we reason about scalable concurrency under realistic assumptions about shared memory? The verification literature almost universally assumes that threads interact through a "strong" (sequentially consistent) shared memory. But modern compilers and CPUs provide much weaker guarantees that cause many previously verified algorithms to fail. I will present GPS, the first program logic to provide a full suite of modular verification techniques under a weak memory model. Aaron Turon is a postdoctoral researcher in the Foundations of Programming group at the Max Planck Institute for Software Systems (MPI-SWS), supervised by Derek Dreyer. He received his Ph.D. from Northeastern University in May 2013 under the supervision of Mitchell Wand, and his BA with Honors at the University of Chicago in 2007. Aaron's interests span programming languages and software verification, but his primary focus for the last several years has been the design and verification of high-performance concurrency libraries.

1 1

Colloquium Speaker John Duchi Wed. Feb. 19, 4:30pm
by Nicole E. Wagenblast 19 Feb '14

19 Feb '14

Computation, Communication, and Privacy Constraints on Learning John Duchi , University of California, Berkeley Wednesday, February 19, 4:30pm Computer Science 105 How can we maximally leverage available resources--such as computation, communication, multi-processors, or even privacy--when performing machine learning? In this talk, I will suggest statistical risk (a rigorous notion of the accuracy of learning procedures) as a way to incorporate such criteria in a framework for development of algorithms. In particular, we follow a two-pronged approach, where we (1) study the fundamental difficulties of problems, bringing in tools from optimization, information theory, and statistical minimax theory, and (2) develop algorithms that optimally trade among multiple criteria for improved performance. The resulting algorithms are widely applied in industrial and academic settings, giving up to order of magnitude improvements in speed and accuracy for several problems. To illustrate the practical benefits that a focus on the tradeoffs of statistical learning procedures brings, we explore examples from computer vision, speech recognition, document classification, and web search. John is currently a PhD candidate in computer science at Berkeley, where he started in the fall of 2008. His research interests include optimization, statistics, machine learning, and computation. He works in the Statistical Artificial Intelligence Lab (SAIL) under the joint supervision of Michael Jordan and Martin Wainwright. He obtained his MA in statistics in Fall 2012, and received a BS and MS from Stanford University in computer science under the supervision of Daphne Koller. John has won several awards and fellowships, including a best student paper award at the International Conference on Machine Learning (ICML) and the NDSEG and Facebook graduate fellowships. John has also worked as a software engineer and researcher at Google Research under the supervision of Yoram Singer and Fernando Pereira.

1 2

Colloquium Speaker: Raluca Popa Tues Feb 18, 4:30pm
by Nicole E. Wagenblast 17 Feb '14

17 Feb '14

Building systems that compute on encrypted data Raluca Popa , Massachusetts Institute of Technology Tuesday, February 18, 4:30pm Computer Science 105 Theft of confidential data is prevalent. In most applications, confidential data is stored at servers. Thus, existing systems naturally try to prevent adversaries from compromising these servers. However, experience has shown that adversaries still find a way to break in and steal the data. In this talk, I will describe a new approach to protecting data confidentiality even when attackers get access to all server data: building practical systems that compute on encrypted data without access to the decryption key. In this setting, I designed and built a database system (CryptDB), a web application platform (Mylar), and two mobile systems, as well as developed new cryptographic schemes for them. I showed that these systems support a wide range of applications with low overhead. The talk will focus primarily on CryptDB and Mylar. My work has already had impact: Google uses CryptDB’s design for their new Encrypted BigQuery service, and a medical application of Boston’s Newton-Wellesley hospital is secured with Mylar. Looking forward, this approach promises to solve privacy problems in other systems, such as big data or genomics systems. Raluca Ada Popa is a PhD candidate at MIT working in security, systems, and applied cryptography. As part of her PhD work, she built practical systems that compute over encrypted data as well as designed new encryption schemes that underlie these systems. Raluca is the recipient of a Google PhD Fellowship for secure cloud computing, Johnson award for best CS Masters of Engineering thesis from MIT, and CRA Outstanding undergraduate award from the ACM. Raluca received her undergraduate degree from MIT with two BS degrees, in computer science and in mathematics.

1 2

Colloquium Speaker Tamara Broderick Wed. Feb 17 4:30pm
by Nicole E. Wagenblast 12 Feb '14

12 Feb '14

Feature allocations, paintboxes, and probability functions Tamara Broderick , University of California, Berkeley Wednesday, February 17, 4:30pm Computer Science 105 Clustering involves placing entities into mutually exclusive categories. We wish to relax the requirement of mutual exclusivity, allowing objects to belong simultaneously to multiple classes, a formulation that we refer to as "feature allocation." The first step is a theoretical one. In the case of clustering the class of probability distributions over exchangeable partitions of a dataset has been characterized (via exchangeable partition probability functions and the Kingman paintbox). These characterizations support an elegant nonparametric Bayesian framework for clustering in which the number of clusters is not assumed to be known a priori. We establish an analogous characterization for feature allocation; we define notions of "exchangeable feature probability functions" and "feature paintboxes" that lead to a Bayesian framework that does not require the number of features to be fixed a priori. The second step is a computational one. Rather than appealing to Markov chain Monte Carlo for Bayesian inference, we develop a method to transform Bayesian methods for feature allocation (and other latent structure problems) into optimization problems with objective functions analogous to K-means in the clustering setting. These yield approximations to Bayesian inference that are scalable to large inference problems. Tamara Broderick is a PhD candidate in the Department of Statistics at the University of California, Berkeley. Her research in machine learning focuses on the design and study of Bayesian nonparametric models, with particular emphasis on feature allocation as a generalization of clustering that relaxes the mutual exclusivity and exhaustivity assumptions of clustering. While at Berkeley, she has been a National Science Foundation Graduate Student Fellow and a Berkeley Fellowship recipient. She graduated with an AB in Mathematics from Princeton University in 2007---with the Phi Beta Kappa Prize for highest average GPA in her graduating class and with Highest Honors in Mathematics. She spent the next two years on a Marshall Scholarship at the University of Cambridge, where she received a Masters of Advanced Study in Mathematics for completion of Part III of the Mathematical Tripos (with Distinction) in 2008 and an MPhil by Research in Physics in 2009. She received a Masters in Computer Science from UC Berkeley in 2013.

1 2

Colloquium Speaker Debora Marks Thurs Feb 6, 4:30pm
by Nicole E. Wagenblast 06 Feb '14

06 Feb '14

Debora Marks , Harvard Medical School Thursday, February 6, 4:30pm Computer Science 105 Abstract: Attributes of living systems are constrained in evolution. An alternative to the analysis of conserved attributes ('characters') is analysis of functional interactions ('couplings') that cause conservation. For proteins, the evolutionary sequence record can be exploited to provide exquisitely accurate information about 3D structures and functional sites. Recent progress is based on high throughput sequencing as an experimental technology and global probability models under the maximum entropy principle as a key theoretical tool. I will describe how these advances are used in accurate prediction of 3D interactions, complexes, protein plasticity, designing proteins for synthetic biology and therapeutics - and extrapolate to the study of the effects of human genetic variation. There is a now major opportunity to link genomic information to phenotype and apply this to concrete engineering and health problems, such as disease likelihood, the emergence of drug resistance. My lab will concentrate on four interrelated areas at different scales of biology that address the challenge to infer causality in biological information. Debora has a PhD in computational biology and a track record of developing novel algorithms and statistics to successfully address unsolved biological problems. She has a passion for statistics and is driven by a desire to understand and interpret human genetic variation.

1 2

4:30pm Wed Mar 12 Cerf & Kahn Public Lecture about the Internet in Friend 101 (arrive early!)
by Jennifer Rexford 04 Feb '14

04 Feb '14

What: Fathers of the Internet reflecting on the evolution of the Internet. (and a celebration of the 40th anniversary of the invention of TCP/IP protocol for the Internet by Cerf & Kahn in 1974.) Who: Vinton Cerf (Chief Internet Evangelist at Google) and Robert Kahn (CEO of Corporation for National Research Initiatives), whose pioneering work on the Internet has been widely recognized by numerous awards, including the US Presidential Medal of Freedom, the US National Medal of Technology, and the ACM Turing Award, will together give a public duet lecture on “Perspectives on the Internet and its Evolution.” When: March 12, 2014. 4:30-5:30pm. Seating starts at 4pm. Where: Princeton University, Friend Center Auditorium 101. Detail: This is an open lecture to general public. No fee or ticket required. Seating available on first-come-first-served basis, and starts at 4pm. Website (including direction): http://edgelab-events.princeton.edu

1 0

C Beck preFPO
by Melissa M. Lawson 28 Jan '14

28 Jan '14

Chris Beck will present his preFPO on Friday Jan 31 at 3PM in Room 402. Everyone is invited to attend his talk. His abstract follows below. ----- Original Message ----- Title: Lower Bounds for Time and Space In this thesis we study the computational limitations of restricted models of computation. We pay particular attention to ``simple'' algorithms for satisfiability, that is, algorithms which are permitted to use large amounts of traditional resources such as space and time, but whose correctness must be provable in a simple proof system. This has the consequence that when an algorithm accepts or rejects an input, the computation history corresponds to a simple propositional proof of the input's status, and that studying the structure of such proofs allows us to formally understand some of the difficulties faced by the algorithm. The fact that many algorithms yield proofs has been observed in a variety of scenarios in both theory and practice. Moreover, in many of these cases, proof complexity is the only known way to analyze the running time of such algorithms. >From a different point of view, our results are interesting because the techniques for proof lower bounds are closely related to the known techniques for circuit lower bounds. Lower bounds for circuits via random restrictions and via Razoborv's method of approximations are closely related to Haken's bottleneck counting method for Resolution lower bounds, and well-known work of Beame et al. shows that this analogy can be carried through even for AC0 Frege proofs. One of our most important contributions to the area is to show that the bottleneck counting technique can also be used to show time space trade-offs. Indeed, while previous time space tradeoffs used ad-hoc techniques and only applied in the sublinear space regime, we show that the same technique which gives (tight) proof size lower bounds can be vastly generalized to yield superpolynomial time space tradeoffs which are tight in the high space regime. It is an interesting question for future research whether our technique could also be used for restricted circuits, such as monotone circuits, or in a model such as read once algebraic branching programs. Our results are the following: - We give the first time space trade-off results for Resolution which are meaningful in the regime of {\emph{ superlinear}} space. More concretely, we give tautologies which have polynomial size resolution proofs which may be carried out in polynomial space (and which standard algorithms would find in polynomial time using polynomial memory), but for which even slightly reduced space entails a superpolynomial size resolution proof. This gives the first formal explanation for why DPLL+Clause Learning SAT solvers need a large amount of space to work well in practice, and gives evidence to support the main conjecture of Allender et al. (2012) regarding tree-width parameterized satisfiability. - We extend these techniques to the stronger Polynomial Calculus Resolution proof system, an algebraic system used sometimes in practice instead of traditional SAT solvers, based on Grobner Basis techniques. - We show that the Strong Exponential Time Hypothesis applies to the proof system of regular resolution, and thus to algorithms based on the original Davis Putnam procedure. We conjecture that SETH holds for general resolution, and improve the state of the art size lower bounds for resolution proofs. In particular, we show that Grover's black box search algorithm solves SAT faster than any classical SAT solver. - We expand upon recent work of Lovett and Viola, giving an explicit distribution of strings which is hard to approximately sample in AC0. Our results are essentially best possible in terms of the size of the circuits and quality of the approximation. In addition we prove a new concentration bound for collections of decision trees, and a structure theorem for these, which could be useful in future applications.

1 0

Tengyu Ma general exam - change of location!
by Melissa M. Lawson 20 Jan '14

20 Jan '14

Tengyu's general exam will now take place in the Sherrerd Hall conference room, Sherrerd 306, this Wednesday Jan 22 from 2-4PM. Sorry for any inconvenience. --Melissa

1 0

Tengyu Ma general exam
by Melissa M. Lawson 17 Jan '14

17 Jan '14

Tengyu Ma will present his research seminar/general exam on Wednesday January 22 at 2PM in Room 301 (note room!). The members of his committee are: Sanjeev Arora (advisor), Moses Charikar, and David Blei. 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 I will mainly talk about our recent paper on deep learning provable bound for learning some deep representations. Deep learning, a modern variant of artificial neural net, has been a very powerful tool in recent years for many machine learning tasks such as image recognition, speech recognition and natural language processing. Variations of However, theoretically, it still remains mysterious why these modern heuristics and tricks together with millions of data result in big improvements in so many important questions. With the motivation to resolve these mysteries, this paper proposes a generative model for deep network, and provides an provable algorithm that can learn all the parameters and hidden variables unsupervisedly using polynomial time and polynomial samples generated from this network under some assumptions In more detail, the network we study has constant number of layers, each consecutive two layers are connected via a random sparse bipartite graph/matrix. The observed data at bottom are generated as follows: First a sparse hidden vector at the top layer is chosen, then the top layer activates some of the second layer nodes by multiplying the connection matrix and applying another point-wise threshold function, and then adding some small noise. Then the second layer activates the third using the same rules with the new connection matrix, so on and so forth. Our algorithms exploits the old Hebbian rule: "Things fire together wire together", that is, if two nodes in the same layer are correlated, then they are likely to connect to the same ancestor in the layer above them. This is the joint work with Sanjeev Arora, Aditya Bhaskara and Rong Ge. Reading list: 0. Algorithm Design, Jon Kleinberg, Éva Tardos 1. Ankur Moitra's lecture notes for the course Algorithmic Aspects of Machine Learning http://people.csail.mit.edu/moitra/996.html 2. Daniel Hsu's lecture notes for COMS 4772 Advanced Machine Learning (Fall 2013) http://www.cs.columbia.edu/~djhsu/4772/ 3. Machine Learning: A Probabilistic Perspective By Kevin P. Murphy (provided I could find it in library) http://mitpress.mit.edu/sites/default/files/titles/content/9780262018029_to… 4. Representation Learning: A Review and New Perspectives, by Yoshua Bengio, Aaron Courville, Pascal Vincent 5. Visualizing and Understanding Convolutional Networks http://arxiv.org/abs/1311.2901 6. ImageNet Classification with Deep Convolutional Neural Networks by Krizhevsky, A., Sutskever, I. and Hinton, G. E. 7. Generalized Denoising Auto-Encoders as Generative Models Bengio et al. http://arxiv.org/abs/1305.6663 8. On the Provable Convergence of Alternating Minimization for Matrix Completion 9. Tensor Decompositions for Learning Latent Variable Models by Anandkumar, Ge, Hsu, Kakade, Telgarsky 10. A. Kumar, R. Kannan, Clustering with Spectral Norm and the k-Means Algorithm 11. V. Chandrasekaran, P. Parrilo, A. Willsky, Latent Variable Graphical Model Selection via Convex Optimization

1 0

J Wetzel general exam
by Melissa M. Lawson 10 Jan '14

10 Jan '14

Joshua Wetzel will present his research seminar/general exam on Friday January 17 at 10AM in Room 302 (note room!). The members of his committee are: Mona Singh, advisor, Olga Troyanskaya, and Tom Funkhouser. 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: Protein-DNA interaction is a fundamental step in cellular regulation. Proteins known as transcription factors (TFs) are produced in order to either enhance or repress the expression of various gene products according to the particular needs of the cell at a given moment. They often do so by binding to the genome in specific locations according to the amino acid residues contained in their DNA-binding domain (DBD), which is the structural unit of the protein that is often used to classify TFs into groups. The largest class of TFs, comprising roughly half of the annotated TFs in eukaryotes, is defined by a DBD known as a Cys 2 His 2 zinc finger (C2H2-ZF). While the majority of DBDs can bind only a limited repertoire DNA sequences, members of the C2H2-ZF class span an extremely wide variety of DNA binding preferences. Moreover, these preferences appear to be determined largely by the identity of amino acids occupying only a few key positions of a structurally well-defined and semi-modular protein-DNA contact interface. However, the rules that govern DNA-binding preferences remain unclear, thwarting our ability to predict binding sites of endogenous C2H2-ZFs. Due to the large number of possible amino-acid combinations and the variety of DNA sequences they can potentially bind, high-throughput interaction screens and rigorous computational methods are necessary. In my talk, I’ll discuss the analysis of a high-throughput, randomized, synthetic screen of C2H2-ZF-DNA functional interactions obtained via the bacterial one-hybrid selection system. After extensive filtering, the data reveals hundreds to thousands of ‘canonical’ helices binding with varying levels of affinity to each of the 64 possible 3bp DNA targets, providing the most comprehensive view of C2H2-ZF-DNA interaction to date. I will explain an information theoretic analysis that validates an expanded view of the physical model for the C2H2-ZF-DNA binding interface and show methods for inferring DNA-binding profiles via integration of data from independent protein selections. Additionally, I extend the predictive scope of the data by adapting a classical nearest neighbors approach by leveraging information related to the physical binding model and frequently observed amino acid substitutions. I will demonstrate strong concordance between predicted binding profiles and their experimentally determined counterparts within the synthetic context, as well as generalizability of the data via prediction of binding profiles for naturally occurring C2H2-ZFs. Overall, the analysis reveals a complex binding landscape for C2H2-ZFs, which shows both agreement and conflict with previously proposed ‘codes’ of DNA-binding specificity. Reading List: 1. Jones, N. C. & Pevzner, P. A. An Introduction to Bioinformatics Algorithms . MIT Press (2004). (Textbook) 2. Stormo, G. D. & Zhao, Y. Determining the specificity of protein-DNA interactions. Nat. Rev. Genet. 11, 751–60 (2010). 3. Persikov, A. V. & Singh, M. An expanded binding model for Cys2His2 zinc-finger protein-DNA interfaces. Phys. Biol. 8 (3):035010 (2011). 4. Noyes, M. et al. A systematic characterization of factors that regulate Drosophila segmentation via a bacterial one-hybrid system. Nucleic Acids Res. 36 (8), 2547-60 (2008). 5. Klug, A. The discovery of zinc fingers and their applications in gene regulation and genome manipulation. Annu. Rev. Biochem. 79, 213–31 (2010). 6. Jolma, A. et al. DNA-binding specificities of human transcription factors. Cell 152, 327–39 (2013). 7. Benos, P. V., Lapedes, A. S. & Stormo, G. D. Probabilistic Code for DNA Recognition by Proteins of the EGR Family. J. Mol. Biol. 323, 701–727 (2002). 8. Enuameh, M. S. et al. Global analysis of Drosophila Cys ₂ -His ₂ zinc finger proteins reveals a multitude of novel recognition motifs and binding determinants. Genome Res. 23, 928–40 (2013). 9. Vaquerizas, J. M., Kummerfeld, S. K., Teichmann, S. a & Luscombe, N. M. A census of human transcription factors: function, expression and evolution. Nat. Rev. Genet. 10, 252–63 (2009). 10. Persikov, A. V & Singh, M. De novo prediction of DNA-binding specificities for Cys2His2 zinc finger proteins. Nucleic Acids Res. 1–12 (2013).

1 0