May 2018 - talks - lists.cs.princeton.edu

Divyarthi Mohan General Exam Presentation TODAY May 23, 2018 11:00 am CS302
by Barbara A. Mooring 23 May '18

23 May '18

Divyarthi Mohan will present General Exam Presentation TODAY May 23, 2018 at 11:00 am in CS302. Committee: Matt Weinberg, Adviser Bernard Chazelle Ran Raz Title: Information Aggregation via non-Bayesian Asynchronous Learning in Trees Abstract: We consider a social network where each person or node has to make a binary decision in a world with a ground truth that one of the two choices is better. For example, each node has to choose red or blue, and the correct choice is red. Each node v has a private signal, X(v) = red or blue, that denotes its belief about the world and these signals are drawn independently from a distribution that is biased towards the truth. Initially all nodes are unannounced and information propagates in the graph through a stochastic process. At each time step, we pick a node uniformly at random to announce its opinion and nodes can update their opinions over time when picked again. Each node can only see its neighbours' latest announcements (and not their private signals). We study how information aggregates when the social network is a tree and the nodes conform to the majority of their neighbours (that have announced). Previously, Feldman et al. showed that when the graph is sparse and expansive, with high probability, the correct consensus is reached. They prove this by showing that in a bounded degree graph, a correct majority is reached in near linear steps; if the graph is an expander, this majority opinion propagates to the whole graph. We show that in any tree, with high probability, after near linear steps the majority of nodes have the correct opinion. We will also further discuss approaches to show that the process stabilizes in a correct majority. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 0

Colloquium Speaker-Daniel Sanchez, Tuesday, May 29
by Emily C. Lawrence 23 May '18

23 May '18

Daniel Sanchez from MIT Tuesday, May 29, 2018 - 12:30pm Computer Science - Room 105 Host: Margaret Martonosi "Making Parallelism Pervasive with the Swarm Architecture" Abstract: With Moore's Law coming to an end, architects must find ways to sustain performance growth without technology scaling. The most promising path is to build highly parallel systems that harness thousands of simple and efficient cores. But this approach will require new techniques to make massive parallelism practical, as current multicores fall short of this goal: they squander most of the parallelism available in applications and are too hard to program. I will present Swarm, a new architecture that successfully parallelizes algorithms that are often considered sequential and is much easier to program than conventional multicores. Swarm programs consist of tiny tasks, as small as tens of instructions each. Parallelism is implicit: all tasks follow a programmer-specified total or partial order, eliminating the correctness pitfalls of explicit synchronization (e.g., deadlock, data races, etc.). To scale, Swarm executes tasks speculatively and out of order, and efficiently speculates thousands of tasks ahead of the earliest active task to uncover enough parallelism. Swarm builds on decades of work on speculative architectures and contributes new techniques to scale to large core counts, including a new execution model, speculation-aware hardware task management, selective aborts, and scalable ordered task commits. Swarm also incorporates new techniques to exploit locality and to harness nested parallelism, making parallel algorithms easy to compose and uncovering abundant parallelism in large applications. Swarm accelerates challenging irregular applications from a broad set of domains, including graph analytics, machine learning, simulation, and databases. At 256 cores, Swarm is 53-561x faster than a single-core system, and outperforms state-of-the-art software-only parallel algorithms by one to two orders of magnitude. Besides achieving near-linear scalability, the resulting Swarm programs are almost as simple as their sequential counterparts, as they do not use explicit synchronization. Bio: Daniel Sanchez is an Associate Professor of Electrical Engineering and Computer Science at MIT. His research interests include parallel computer systems, scalable and efficient memory hierarchies, architectural support for parallelization, and architectures with quality-of-service guarantees. He earned a Ph.D. in Electrical Engineering from Stanford University in 2012 and received the NSF CAREER award in 2015.

1 0

Jude Nelson FPO TOMORROW May 22, 2018 2:00 pm - CS402
by Barbara A. Mooring 22 May '18

22 May '18

Jude Nelson will present his FPO TOMORROW May 22, 2018 at 2:00 pm in CS402. Committee: Larry Peterson, Adviser - Princeton University Kai Li - Princeton University Brian Kernighan - Princeton University John H. Hartman - University of Arizona All are welcomed to attend. Title: Wide-area Software-defined Storage Abstract: The proliferation of commodity cloud services helps developers build wide-area \system-of-systems" applications by harnessing cloud storage, CDNs, and public datasets as reusable building blocks. But to do so, developers must contend with two long-term challenges. First, whenever developers change storage providers, they must work to preserve the application's expected storage semantics, i.e. the rules governing how the application expects the storage provider to handle its reads and writes. Today, changing storage providers is costly, because developers need to patch the application to make it compatible with the new provider's data consistency model, access controls, replica placement strategies, and so on. At the same time, users have certain expectations about how their data will be used, which the application must meet. For example, depending on the application, users may expect that their data will be kept private from other users, that their data will be exportable to other applications, that accesses to their data will be logged in an auditable way, and so on. In the limit, each user's expectations represent an implicit policy constraining how their data can be stored. Honoring these policies is dicult for developers who rely on third-party storage providers because the storage provider is often unaware of them. This thesis addresses these challenges with a wide-area storage protocol, called \software-dened storage" (SDS), that runs in-between applications and cloud services. SDS-enabled applications do not host data, but instead let users bring their preferred cloud services to the application. By taking a user-centric approach to hosting data, users are empowered to programmatically specify their policies independent of their applications and select services that will honor them. To support this approach and to tolerate service provider changes, SDS empowers developers to programmatically specify their application's storage semantics independent of storage providers. This thesis presents the design principles for SDS, and validates their real-world applicability with two SDS implementations and several non-trivial applications built on top of them. Most of these applications are used in production today. This thesis presents early performance results of its SDS implementations and uses real-world experiences to show how to make the most of SDS. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 1

Huiwen Chang FPO TOMORROW May 22, 2018 1:00 pm CS 401
by Barbara A. Mooring 22 May '18

22 May '18

Huiwen Chang will present her FPO TOMORROW May 22, 2018 at 1:00 pm in CS 401 Committee: Adam Finkelstein, Adviser Princeton University Olga Russakovsky - Princeton University) David Dobkin - Princeton University Syzmon Rusinkiewicz- Princeton Unviersity All are welcomed to attend. Title: PERSONAL PHOTO ENHANCEMENT Abstract: Thanks to the democratization of digital cameras and camera-equipped smartphones, casual photographers have an increasing need to be able to easily enhance their growing personal photo collections. Existing commercial tools for photo enhancement are either expressive but too sophisticated for casual photographers (e.g. Adobe Photoshop), or easy-to-use but limited in expressiveness (e.g. one-click filters from Instagram). This poses the challenge of how to enable novices to easily edit and enhance their personal photo collections. This thesis describes three systems that collectively build a foundation for solving the practical problem of enhancing personal photo collections as a whole. Our goal is to enhance a personal photo collection, and the first challenge is to select which photos in the collection are worth keeping, editing and sharing. In particular we would like to automatically exclude bad photos from a series of shots taken of the same scene. Note that this goal takes a different perspective from that of previous work, for two reasons. First, casual personal photos have different statistics from those of general images. Second, the problem of selecting which are the best photos in a series of similar shots is different from establishing an overall quality measure for any single photo in isolation. Next, the thesis studies the color transfer problem on photo enhancement. Because visual taste is personal, an enhancement tool is necessary to provide users with both enough freedom and intuitive control. Therefore, additional to a novel color transfer algorithm, we also design a simple interface for making color exploration easy and intuitive. When taking a photo collection as a whole, the color transfer algorithm can also be applied to enhance the overall color consistency among multiple photos automatically, which also enables users to tune their entire photo album simultaneously. Finally, we narrow down photo enhancement to specific domains and focus on portraiture in personal photo collections. We propose a novel framework for modifying portrait images to match with the style of another person in a reference photo, and in particular, we explore the application of this technique towards transferring makeup styles. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 1

Chaitanya Aluru General Exam Presentation Monday May 21, 2018 at 11:00 am in CS302
by Barbara A. Mooring 21 May '18

21 May '18

Chaitanya Aluru will present his General Exam Presentation on Monday May 21, 2018 at 11:00 am in CS302 Title: Reconciliation Methods for Transcription Factor Evolution Abstract: Regulatory networks are thought to underlie the biological differences between organisms. However, the evolutionary mechanisms by which these networks evolve is still an active area of research. Proteins called transcription factors (TFs) form a central component of regulatory networks and are thought to evolve through repeated duplications and losses of component domains. The current framework for inferring ancestral evolutionary events in proteins models single domain duplications, losses and transfers. However, recent work has shown that rapid evolution of some transcription factors was driven by tandem domain duplications rather than individual duplications, making inference by current models incorrect. In this talk, I will discuss the unique challenges that arise in inferring ancestral evolutionary events in TFs, using zinc finger proteins as a model of rapid evolutionary expansion. I then propose extensions to the model to appropriately account for the greater set of evolutionary events that affect TFs. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 1

Zeyu Jin FPO Monday May 21, 2018 at 1:00 pm CS401
by Barbara A. Mooring 18 May '18

18 May '18

Zeyu Jin will present his FPO on Monday, May 21 at 1:00 pm in CS401 Committee: Adam Finkelstein, Adviser Princeton University Szymon Rusinkiewicz - Princeton University Marshini Chetty - Princeton University All are welcome to attend. Title: Speech Synthesis for Text-Based Editing of Audio Narration Abstract: Recorded audio narration plays a crucial role in many contexts including online lectures, documentaries, demo videos, podcasts, and radio. However, editing audio narration using conventional software typically involves many painstaking low-level manipulations. Some state of the art systems allow the editor to perform select, cut, copy and paste operations in the text transcript of the narration and apply the changes to the waveform accordingly. However such interfaces do not support the ability to synthesize new words not appearing in the transcript. While it is possible to build a high fidelity speech synthesizer based on samples of a new voice, to operate well they typically require a large amount of voice data as input as well as substantial manual annotation. This thesis presents a speech synthesizer tailored for text-based editing of narrations. The basic idea is to synthesize the input word in a different voice using a standard pre-built speech synthesizer and then transform the voice to the desired voice using voice conversion. Unfortunately, conventional voice conversion does not produce synthesis with sufficient quality for the stated application. Hence, this thesis introduces new voice conversion techniques that synthesize words with high individuality and clarity. Three methods are proposed: the first approach is called CUTE, a data-driven voice conversion method based on frame-level unit selection and exemplar features. The second method called VoCo is built on CUTE but with several improvements that help the synthesized word blend more seamlessly into the context where it is inserted Both CUTE and VoCo select sequences of audio frames from the voice samples and stitch them together to approximate the voice being converted. The third method improves over VoCo with deep neural networks. It involves two networks: FFTNet generates high quality waveforms based on acoustic features, and TimbreNet transforms the acoustic feature of the generic synthesizer voice to that of a human voice. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 1

Divyarthi Mohan General Exam Presentation Wednesday, May 23, 2018 at 11:00 am CS302
by Barbara A. Mooring 18 May '18

18 May '18

Divyarthi Mohan will present her General Exam Presentation on Wednesday, May 23, 2018 at 11:00 am in CS302. Committee: Matt Weinberg (Adviser) Bernard Chazelle Ran Raz Title: Information Aggregation via non-Bayesian Asynchronous Learning in Trees Abstract: We consider a social network where each person or node has to make a binary decision in a world with a ground truth that one of the two choices is better. For example, each node has to choose red or blue, and the correct choice is red. Each node v has a private signal X(v) 2 fred, blueg that denotes its belief about the world and these signals are drawn independently from a distribution that is biased towards the truth. Initially all nodes are unannounced and information propagates in the graph through a stochastic process. At each time step, we pick a node uniformly at random to announce its opinion and nodes can update their opinions over time when picked again. Each node can only see its neighbours' latest announcements (and not their private signals). We study how information aggregates when the social network is a tree and the nodes conform to the majority of their neighbours (that have announced). Previously, Feldman et al. showed that when the graph is sparse and expansive, with high probability, the correct consensus is reached. They prove this by showing that in a bounded degree graph, a correct majority is reached in near linear steps; if the graph is an expander, this majority opinion propagates to the whole graph. We show that in any tree, with high probability, after near linear steps the majority of nodes have the correct opinion. We will also further discuss approaches to show that the process stabilizes in a correct majority. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 0

Gregory Gundersen General Exam Presentation Monday, May 21, 2018 at 3:00 pm - CS301
by Barbara A. Mooring 18 May '18

18 May '18

Gregory Gundersen will present his General Exam Presentation on Monday, May 21, 2018 at 3:00 pm in CS301. Committee: Barbara Engelhardt (Adviser) Ryan Adams Mona Singh Title: Multimodal embeddings with structured priors Abstract: Medical images are visually evaluated by experts for key morphological features, but the genes underlying particular features are typically unknown. We propose a multimodal modeling and inference framework that learns modality-specific and interpretable latent representations of both genetic variation and medical image features. The method uses deep canonical correlation analysis (DCCA) to correlate paired embeddings. One modality's embeddings are constrained by a generative prior using a variational autoencoder (VAE). The full model is trained end-to-end with a loss function that combines the DCCA and VAE objectives. We demonstrate utility of this method by exploring the task of jointly learning point cloud clusters of histology slides and gene expression levels and recovering known biological knowledge. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 0

Ryan Amos General Exam Presentation May 21, 2018 at 1:00 pm in CS301
by Barbara A. Mooring 17 May '18

17 May '18

Ryan Amos will present General Exam Presentation May 21, 2018 at 1:00 pm in CS301. Title: Verifiable Random Beacons Abstract: Random beacons sources of open, public randomness, and play a critical role in many protocols. Their uses range from proofs of earliest possible creation date to secure multiparty computation to lottery systems. Existing sources of public randomness, including various random beacons, are subject to single points of failure, such that an opportunistic adversary might be able to meaningfully affect the outcome. We develop a random beacon that always requires compromising more than one party to meaningfully affect the outcome. In order to further discourage dishonest behavior, every critical step of our protocol is third-party auditable and backed by economic incentives that make honest behavior more profitable than dishonest behavior. Our method uses a variant of a verifiable random function (VRF) to "scramble" a public input in an unpredictable, thresholded manner, making it difficult for anyone one party to predict how changes to the public input affect the output, or to affect or suppress the output. The proofs of the VRFs are verified by smart contracts to provide monetary reward or penalty, as appropriate, to protocol participants, ensuring honesty is the best fiscal policy. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 0

Haoyu Zhang FPO on Thursday, 5/17/2018, at 1:00 pm in CS 302.
by Barbara A. Mooring 17 May '18

17 May '18

Haoyu Zhang will present his FPO on Thursday, 5/17/2018, at 1:00pm in CS 302. The members of his committee are Mike Freedman (advisor), Kyle Jamieson, Wyatt Lloyd (readers), Kai Li, Jennifer Rexford (examiners). Title: Resource Management for Advanced Data Analytics at Large Scale Abstract: The rapidly growing size of data and the complexity of analytics present new challenges for large-scale data analytics systems. Modern distributed computing frameworks need to support not only embarrassingly parallelizable batch jobs, but also advanced applications analyzing text and multimedia data using complex queries and machine learning (ML) models. Given the computation and storage costs of advanced data analytics, resource management is crucial. New applications and workloads expose vastly different characteristics which make traditional scheduling systems inadequate, and at the same time offer great opportunities that lead to new system designs for better performance. In this thesis, we present resource management systems that significantly improve cloud resource efficiency by leveraging the specific characteristics of advanced data analytics applications. We present the design and implementation of the following systems: (i) VideoStorm: a video analytics system that scales to process thousands of vision queries on live video streams over large clusters. VideoStorm's offline profiler generates resource-quality profiles for vision queries, and its online scheduler allocates resources to maximize performance in terms of vision processing quality and lag. (ii) SLAQ: a cluster scheduling system for approximate ML training jobs that aims to maximize the overall model quality. In iterative and exploratory training settings, better models can be obtained faster by directing resources to jobs with the most potential for improvement. SLAQ allocates resources to maximize the cluster-wide quality improvement based on highly-tailored model quality predictions. (iii) Riffle: an optimized shuffle service for big-data analytics frameworks that significantly improves I/O efficiency. The all-to-all data transfer (i.e., shuffle) in modern big-data systems (such as Spark and Hadoop) becomes the scaling bottleneck for multi-stage analytics jobs, due to the superlinear increase in disk I/O operations as data volume grows. Riffle boosts system performance by merging fragmented intermediate files and efficiently scheduling the merge operations. Taken together, this thesis demonstrates a novel set of methods in both job-level and task-level scheduling for building scalable, highly-efficient, and cost-effective resource management systems. We have performed extensive evaluation with real production workloads, and our results show significant improvement in resource efficiency, job completion time, and system throughput for advanced data analytics. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 2