- talks - lists.cs.princeton.edu

Colloquium Speaker Sebastian Burckhardt Thurs Nov 20, 4:30pm
by Nicole E. Wagenblast 14 Nov '14

14 Nov '14

Colloquium Speaker Sebastian Burckhardt , from Microsoft Research Thursday, November 20, 2014 - 4:30pm Computer Science Small Auditorium (Room 105) Robust Abstractions for Replicated Shared State In the age of cloud-connected mobile devices, users want responsive apps that read and write shared data everywhere, at all times, even if network connections are slow or unavailable. Replication and eventual consistency, while able to deliver this experience, require us to face the complexity of asynchronous update propagation and conflict resolution. Our research goal is to find abstractions that encapsulate this complexity, in order to simplify the programming of distributed applications that are responsive, reactive, and collaborative. In this talk, we first discuss the general principles of eventual consistency. Then, we introduce our programming model, consisting of cloud types (for declarative type-based conflict resolution) and the GLUT model (an operational consistency model based on a global log of update transactions). Finally, we report on our practical experiences with supporting cloud types and GLUT in the TouchDevelop programming language and mobile development environment. Sebastian Burckhardt was born and raised in Basel, Switzerland, where he studied Mathematics at the local University. During an exchange year at Brandeis University, he discovered his affinity to Computer Science and immigrated to the United States. After a few years of industry experience at IBM, he returned to academia and earned his PhD in Computer Science at the University of Pennsylvania. Since then, he has worked as a researcher at Microsoft Research in Redmond. His general research interest is the study of programming models for of concurrent, parallel, and distributed systems. More specific interests include consistency models, concurrency testing, self-adjusting computation, and the concurrent revisions programming model.

1 0

ORFE Optimization Seminar: Moses Charikar, Thursday, Nov 20th at 4:30pm, Sherrerd Hall 101
by Nicole E. Wagenblast 13 Nov '14

13 Nov '14

************************************************************************************** === ORFE Optimization Seminar === DATE: Thursday, November 20, 2014 TIME: 4:30pm ***new time*** LOCATION: Sherrerd Hall room 101 ***new room*** SPEAKER: Moses Charikar, Computer Science Dept., Princeton University TITLE: Spectral Embedding of k-Cliques, Graph Partitioning and k-Means ABSTRACT: We introduce and study a new notion of graph partitioning, intimately connected to k-means clustering. Informally, our graph partitioning objective asks for the optimal spectral simplification of a graph as a disjoint union of k normalized cliques. It is a variant of graph decomposition into expanders (where expansion is not measured w.r.t. the induced graph). Optimizing this new objective is equivalent to clustering the effective resistance embedding of the original graph. Our semidefinite programming based approximation algorithm for the new objective is closely related to spectral clustering: it optimizes the k-means objective on a certain smoothed version of the resistive distance embedding. We also show that spectral clustering applied directly to the original graph gives guarantees for our new objective function. In order to illustrate the power of our new notion, we show that approximation algorithms for our new objective can be used in a black box fashion to approximately recover a partition of a graph into k pieces given a guarantee that a good partition exists with sufficiently large gap in internal and external conductance. Joint work with Pranjal Awasthi, Ravishankar Krishnaswamy, and Ali Kemal Sinop. **************************************************************************************

1 0

Colloquium Speaker Emma Brunskill Wed Nov 19, 4:30pm
by Nicole E. Wagenblast 13 Nov '14

13 Nov '14

Colloquium Speaker Emma Brunskill , Carnegie Mellon University Wednesday, November 19, 2014 - 4:30pm Computer Science 105 Interactive ML for People: The Small Data Problem Consider an intelligent tutoring system or an autonomous decision support tool for a doctor. Though such systems may in aggregate have a huge amount of data, the data collected for a single individual is typically very small, and the policy space (of what to next teach a student or how to help treat a patient) is enormous. I will describe two machine learning efforts to tackle these small data challenges: learning across multiple tasks, and better use of previously collected task data, where tasks in both cases involve sequential stochastic decision processes (reinforcement learning and bandits). I will also present results of how one of these techniques allowed us to substantially increase engagement in an educational game to teach fractions. Emma Brunskill is an assistant professor in the computer science department at Carnegie Mellon University. She is also affiliated with the machine learning department at CMU. She works on reinforcement learning, focusing on applications that involve artificial agents interacting with people, such as intelligent tutoring systems. She is a Rhodes Scholar, Microsoft Faculty Fellow and NSF CAREER award recipient, and her work has received best paper nominations in Education Data Mining (2012, 2013) and CHI (2014).

1 0

Colloquium Speaker Ryan Adams Today, 4:30pm
by Nicole E. Wagenblast 13 Nov '14

13 Nov '14

Better Science Through Better Bayesian Computation Ryan Adams, Harvard University Thursday, November 13, 4:30pm Computer Science 105 As we grapple with the hype of "big data" in computer science, it is important to remember that the data are not the central objects: we collect data to answer questions and inform decisions in science, engineering, policy, and beyond. In this talk, I will discuss my work in developing tools for large-scale data analysis, and the scientific collaborations in neuroscience, chemistry, and astronomy that motivate me and keep this work grounded. I will focus on two lines of research that I believe capture an important dichotomy in my work and in modern probabilistic modeling more generally: identifying the "best" hypothesis versus incorporating hypothesis uncertainty. In the first case, I will discuss my recent work in Bayesian optimization, which has become the state-of-the-art technique for automatically tuning machine learning algorithms, finding use across academia and industry. In the second case, I will discuss scalable Markov chain Monte Carlo and the new technique of Firefly Monte Carlo, which is the first provably correct MCMC algorithm that can take advantage of subsets of data. Ryan Adams is an Assistant Professor of Computer Science at Harvard University, in the School of Engineering and Applied Sciences. He leads the Harvard Intelligent Probabilistic Systems group, whose research focuses on machine learning and computational statistics, with applied collaborations across the sciences. Ryan received his undergraduate training in EECS at MIT and completed his Ph.D. in Physics at Cambridge University as a Gates Cambridge Scholar under David MacKay. He was a CIFAR Junior Research Fellow at the University of Toronto before joining the faculty at Harvard. His Ph.D. thesis received Honorable Mention for the Leonard J. Savage Award for Bayesian Theory and Methods from the International Society for Bayesian Analysis. Ryan has won paper awards at ICML, AISTATS, and UAI, and received the DARPA Young Faculty Award.

1 0

Distinguished Colloquium Speaker Dahlia Malkhi, Tues Nov 18, 4:30pm
by Nicole E. Wagenblast 12 Nov '14

12 Nov '14

Distinguished Colloquium Speaker Dahlia Malkhi, until recently from Microsoft Research, Silicon Valley Tuesday, November 18, 4:30pm Computer Science 105 CorfuDB: Transactional Data Services over a Shared Log Conventional wisdom has it that the only way to scale replicated services is by partitioning the data. What would you do if given an infrastructure that breaks the seeming tradeoff between consistency and scale? The talk will describe our experience with building CorfuDB, a distributed fabric that drives consistency and transactional guarantees at high-throughput. CorfuDB facilitates building distributed services in which in-memory data-structures are backed by a shared log. The core is built around the CORFU log, which clients can append-to and read-from over a network. Internally, CORFU is distributed over a cluster of machines with no single I/O bottleneck to either appends or reads. Atop CORFU is Tango, a fabric for programming transactional data services such as the Hyder DB and an Apache-ZooKeeper alternative. Dahlia Malkhi has been a principal researcher at Microsoft Research, Silicon Valley from 2004 until the lab shut down in Sep 2014. She works on applied and foundational research in reliability, consistency and security of distributed computing since the early nineties. Prior to joining Microsoft Research, Dr. Malkhi was an associate professor at the Hebrew University of Jerusalem (1999-2007), left for a brief sabbatical, but was bitten by the Silicon Valley bug and remained at Microsoft. She holds a PhD (1994), M.Sc and B.Sc in computer science from the Hebrew University of Jerusalem, making her the only CS faculty to return to the Hebrew U. for all four academic stages. Dr. Malkhi was elected an ACM fellow in 2011, received the IBM Faculty award in 2003 and 2004 and the German-Israeli Foundation (G.I.F.) Young Scientist award in 2002. She serves on the editorial boards of the IEEE Transactions of Dependable and Secure Computing and of the Distributed Computing Journal. She chaired LADIS 2012 , Locality 2007, PODC 2006, Locality 2005 and DISC 2002.

1 0

Colloquium Speaker Ryan Adams Thurs Nov 13, 4:30pm
by Nicole E. Wagenblast 12 Nov '14

12 Nov '14

Better Science Through Better Bayesian Computation Ryan Adams, Harvard University Thursday, November 13, 4:30pm Computer Science 105 As we grapple with the hype of "big data" in computer science, it is important to remember that the data are not the central objects: we collect data to answer questions and inform decisions in science, engineering, policy, and beyond. In this talk, I will discuss my work in developing tools for large-scale data analysis, and the scientific collaborations in neuroscience, chemistry, and astronomy that motivate me and keep this work grounded. I will focus on two lines of research that I believe capture an important dichotomy in my work and in modern probabilistic modeling more generally: identifying the "best" hypothesis versus incorporating hypothesis uncertainty. In the first case, I will discuss my recent work in Bayesian optimization, which has become the state-of-the-art technique for automatically tuning machine learning algorithms, finding use across academia and industry. In the second case, I will discuss scalable Markov chain Monte Carlo and the new technique of Firefly Monte Carlo, which is the first provably correct MCMC algorithm that can take advantage of subsets of data. Ryan Adams is an Assistant Professor of Computer Science at Harvard University, in the School of Engineering and Applied Sciences. He leads the Harvard Intelligent Probabilistic Systems group, whose research focuses on machine learning and computational statistics, with applied collaborations across the sciences. Ryan received his undergraduate training in EECS at MIT and completed his Ph.D. in Physics at Cambridge University as a Gates Cambridge Scholar under David MacKay. He was a CIFAR Junior Research Fellow at the University of Toronto before joining the faculty at Harvard. His Ph.D. thesis received Honorable Mention for the Leonard J. Savage Award for Bayesian Theory and Methods from the International Society for Bayesian Analysis. Ryan has won paper awards at ICML, AISTATS, and UAI, and received the DARPA Young Faculty Award.

1 0

Talk: Masoud Moshref visit Wed Nov 12 2014
by Nicole E. Wagenblast 11 Nov '14

11 Nov '14

Speaker: Masoud Moshref (USC) Title: Resource Virtualization for Software-defined Networks Date/time: 12-1.30pm Wednesday Nov 12 (lunch provided) Location: COS 402 Abstract: Software defined networking centralizes control plane functionality, separating it from the data plane which is responsible for packet forwarding. Many management tasks such as finding heavy hitters for multi-path routing may run using SDN in a network with limited resources. However, by abstracting them from resources at individual switches, a resource manager at the controller can optimize their resource usage. As management tasks often have a measurement-control loop, my projects, DREAM and vCRIB, work on measurement and control tasks, respectively: First, Dream ensures a minimum user-specified level of accuracy for tasks instead of allocating a fixed amount of resources to each task. Therefore, it dynamically allocates resources across tasks in reaction to traffic dynamics and task dynamics, which allows resource multiplexing. DREAM is 2x better at the tail of minimum accuracy satisfaction comparing to current practice even in cases with moderate load. Next, vCRIB automatically distributes control rules on all switches in the network giving the abstraction of a centralized rule repository with resources equal to the combined resources of all switches. vCRIB can find feasible rule placement with less than 10% traffic overhead in cases where traffic-optimal rule placement is not feasible with respect to CPU and memory constraints. Bio: Masoud Moshref is a 5th year PhD candidate in University of Southern California. He works on resource virtualization in Software-Defined Networks in Networked Systems Lab under supervision of Ramesh Govindan and Minlan Yu. He got MSc and BSc in Information Technology Engineering from Sharif University of Technology in Iran.

1 0

Talk: Yaron Koral Wed Nov 12, 10am
by Nicole E. Wagenblast 11 Nov '14

11 Nov '14

Deep Packet Inspection as a Service Yaron Koral, Princeton University Wednesday, November 12, 10am Computer Science, Room 402 Middleboxes play a major role in contemporary networks, as forwarding packets is often not enough to meet operator demands, and other functionalities (such as security, QoS/QoE provisioning, and load balancing) are required. Traffic is usually routed through a sequence of such middleboxes, which either reside across the network or in a single, consolidated location. Although middleboxes provide a vast range of different capabilities, there are components that are shared among many of them. A task common to almost all middleboxes that deal with L7 protocols is Deep Packet Inspection (DPI). Today, traffic is inspected from scratch by all the middleboxes on its route. In this paper, we propose to treat DPI as a service to the middleboxes, implying that traffic should be scanned only once, but against the data of all middleboxes that use the service. The DPI service then passes the scan results to the appropriate middleboxes. Having DPI as a service has significant advantages in performance, scalability, robustness, and as a catalyst for innovation in the middlebox domain. Moreover, technologies and solutions for current Software Defined Networks (SDN) (e.g., SIMPLE [41]) make it feasible to implement such a service and route traffic to and from its instances. This is joint work with Anat Bremler-Barr, Yotam Harchol, and David Hay, and will appear at CoNEXT in December 2014. Yaron received his PhD at Tel Aviv University and is a new postdoc at Princeton.

1 1

Joey Dodds will present his pre-FPO on November 11 at 9am in Room 402.
by Nicki Gotsis 10 Nov '14

10 Nov '14

Joey Dodds will present his pre-FPO on Tuesday, November 11 at 9am in Room 402. The members of his committee are: Andrew Appel (advisor); David Walker and Jesper Bengtson, I.T. University of Copenhagen (readers); Sharad Malik and Aarti Gupta, NEC Labs America (nonreaders). Everyone is invited to attend his talk. The talk title and abstract follow below: "Symbolic Execution of C Programs by Computational Reflection" Verified Software Toolchain (VST) is a system for proving functional properties about C programs. It is completely implemented and proved correct in the Coq interactive proof assistant. VST is composed of a logic which allows a user to specify and reason about C programs, and Floyd, a proof automation system that allows forward symbolic execution of programs with their specifications. Floyd is implemented in Coq's tactic language, Ltac. There are two major problems with Ltac: as automation built in Ltac proceeds, Coq keeps a record of the steps that have been taken, called proof objects, that allow proofs to be checked once they are complete. These proofs can be large and very complex, causing Ltac automation to be both slow and memory hungry. The second problem with Ltac is that the flexibility of the language can lead to poor practices and slow execution. The Ltac match statement is the main cause of this issue. It allows matches against expressions of arbitrary type, and it allows backtracking when the body of a match fails. These combine to lead to confusing control flows, and slower execution than would be expected for a typed match with no backtracking. Fortunately, a technique known as computational reflection solves the problems associated with Ltac automation. Computational reflection allows automation without storing proof objects, greatly increasing speed while decreasing required memory. It also allows for principled and predictable implementations of algorithms that can be more robust and efficient than their Ltac counterparts. This thesis solves the problems with ltac by implementing reflective automation in two ways. The first is small-scale reflection. Small-scale reflection is built into the logic of VST, and uses computation to specify and check properties of programs within the logic rules. This has benefits regardless of the automation used because no proof objects need to be built about them because the computation itself is the proof. Large-scale reflection replaces the Ltac implementation of Floyd with symbolic execution by reflection. This is done using the MirrorCore library of Malecha et al. MirrorCore presents a general syntax capable of representing any Coq term, allowing computational reasoning where it would normally be impossible. Small-scale and large-scale reflection interact nicely because a well-designed large-scale reflection library will immediately be able to make use of the computation that is done as part of small-scale reflection.

1 0

Colloquium Speaker Greg Corrado today 4:30pm
by Nicole E. Wagenblast 10 Nov '14

10 Nov '14

Google Strength Neural Networks Greg Corrado, Research at Google Monday, November 10, 4:30pm Computer Science 105 Industrial scale applications of machine learning are surprisingly important in the products and services we enjoy today. Over the last few years classical artificial neural networks have reemerged as one of the most powerful, practical machine learning tools available. More than it was driven by algorithmic advances, this “deep learning” renaissance has been fueled by the availability of ever larger data stores and clever use of vast computational resources. Greg will describe Google's large scale distributed neural network framework and the applications of neural networks to the domains of image recognition, speech recognition, and text understanding. Greg Corrado is a senior research scientist at Google working in artificial intelligence, computational neuroscience, and scalable machine learning. He has worked for some time on brain inspired computing, and most recently has served as one of the founding members and a technical lead on Google's large scale deep learning project. Before coming to Google, he worked at IBM Research on the SyNAPSE neuromorphic silicon chip. He did his graduate work in Neuroscience and in Computer Science at Stanford University, and his undergraduate in work Physics at Princeton University.

1 0