- talks - lists.cs.princeton.edu

Steven Englehardt will present his FPO "Automated discovery of privacy violations on the web" on Friday, 6/29/2018 at 10:00am in CS 402.
by Nicki Gotsis 20 Jun '18

20 Jun '18

Steven Englehardt will present his FPO "Automated discovery of privacy violations on the web" on Friday, 6/29/2018 at 10:00am, 402 Computer Science. All are welcome to attend. The members of his committee are as follows: Examiners: Arvind Narayanan (Adviser), Prateek Mittal (ELE), and Jennifer Rexford; Readers: Ed Felten, Nick Feamster Abstract follows below. Tracking protection provided by browsers is often ine↵ective, while solutions based on voluntary cooperation, such as Do Not Track, haven’t had meaningful adoption. Knowledgeable users may turn to anti-tracking tools for protection, but we find that even these more advanced solutions fail to fully protect against the techniques we study. In this dissertation, we introduce OpenWPM, a platform we developed for flexible and modular web measurement. We’ve used OpenWPM to run large-scale studies leading to the discovery of numerous privacy and security violations across the web and in emails. These discoveries have curtailed the adoption of tracking techniques, and have informed policy debates and browser privacy decisions. In particular, we present novel detection methods and results for persistent tracking techniques, including: device fingerprinting, cookie syncing, and cookie respawning. Our findings include sophisticated fingerprinting techniques never before measured in the wild. We’ve found that nearly every new API is misused by trackers for fingerprinting. The misuse is often invisible to users and publishers alike, and in many cases was not anticipated by API designers. We take a critical look at how the API design process can be changed to prevent such misuse in the future. We also explore the industry of trackers which use PII-derived identifiers to track users across devices, and even into the o✏ine world. To measure these techniques, we develop a novel bait technique, which allows us to spoof the presence of PII on a large number of sites. We show how trackers exfiltrate the spoofed PII through the abuse of browser features. We find that PII collection is not limited to the web—the act of viewing an email also leaks PII to trackers. Overall, about 30% of emails leak the recipient’s email address to one or more third parties. Finally, we study the ability of a passive eavesdropper to leverage tracking cookies for mass surveillance. If two web pages embed the same tracker, then the adversary can link visits to those pages from the same user even if the user’s IP address varies. We find that the adversary can reconstruct 62—73% of a typical user’s browsing history

1 0

Jieming Mao FPO Thursday June 14, 2018 10:00 CS 402
by Barbara A. Mooring 14 Jun '18

14 Jun '18

Jieming Mao will present his FPO on Thursday June 14, 2018 at 10:00 in room CS 402. Committee: Mark Braverman, Adviser - Princeton University Elad Hazan - Princeton University Ran Raz - Princeton University All are welcomed to attend. Title: Algorithms in Strategic or Noisy Environments Abstract: Algorithms are often used to interact with agents. When the input is collected from agents instead of being directly given, designing algorithms becomes more challenging. Two main challenges arise here: (i) agents may lie to maximize their own utility functions and we need to take their incentives into account (ii) the uncertainty in agents' behavior makes the input appear to be noisy. In this thesis, we study these two challenges in several contexts: the multi-armed bandit problem, combinatorial auctions and rank aggregation. Our goal is to understand how these strategic and noisy factors make the problem harder and to design new techniques which make algorithms robust against these factors. In Part I (Chapter 2 and Chapter 3), we study multi-armed bandit algorithms in strategic environments where rewards are decided by actions taken by strategic agents. We show that traditional multi-armed bandit algorithms could fail and we also develop multi-armed bandit algorithms which achieve good performance in strategic envrionments. In Part II (Chapter 4 and Chapter 5), we focus on combinatorial auctions which are a natural testbed for truthful mechanisms. We characterize the power of truthful mechanisms in several settings and make progress in understanding whether truthful mechanisms are as powerful as algorithms. In Part III (Chapter 6, Chapter 7 and Chapter 8), we study the top-k ranking problem. In this problem, even if the agents are perfectly incentivized, their reported comparison results could still be noisy caused by reasons like limit of knowledge and subjective preferences. We design algorithms which aggregate noisy comparisons to output the set of top items. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 2

Sivakanth Gopi FPO June 11, 2018 10:00 am CS 402
by Barbara A. Mooring 08 Jun '18

08 Jun '18

Sivakanth Gopi will present his FPO on June 11, 2018 at 10:00 am in room CS 402. All are welcomed to attend. Committee: Zeev Dvir, Adviser - Princeton University Ran Raz - Princeton University Avi Wigderson - Institute for Advanced Study Title: Locality in Coding Theory Abstract: Error correcting codes have been extremely successful in practice to build storage and communication systems which are resilient to noise and corruptions. They also found several theoretical applications in complexity theory, pseudorandomness, probabilistically checkable proofs and cryptography. Each application requires codes with specific properties. One such property desirable in many applications is ‘locality’. Locality refers to the ability to perform operations like decoding/correction/testing in sublinear or sometimes constant time. For example, a constant query locally decodable code (LDC) allows decoding of any message bit in constant time given a corrupted encoding of the message. Much of the work in this thesis is to understand the power and limitations of codes with locality. We show that one can get non-trivial locality and still match the best known rate-distance tradeoffs of traditional error correcting codes (Gilbert- Varshamov bound). We prove several conditional lower bounds on codes with locality and give new directions for constructing such codes by showing an analytic characterization of LDCs. We also explore applications of such codes to additive combinatorics, information privacy and data storage. We show how to use ideas from existing constructions of LDCs to design 2-server private information retrieval schemes where a user can efficiently and privately query a database replicated among two (non-communicating) servers without revealing any information about their query to either server. We also show limits and improved constructions of maximally recoverable local reconstruction codes which are locally correctable codes designed specifically for distributed data storage applications. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 1

Amy Tai PreFPO Wednesday, June 6, 2018 1:00 pm CS402
by Barbara A. Mooring 06 Jun '18

06 Jun '18

Amy Tai will present her PreFPO on Wednesday, June 6, 2018 at 1:00 pm in CS 402. Committee: Mike Freedman (advisor) Jen Rexford Kai Li Kyle Jamieson Wyatt Lloyd All are welcomed to attend. Title: Leveraging Distributed Storage Redundancy in Datacenters Abstract: Replication is a widely used primitive in distributed storage systems to achieve properties such as durability and availability. In this talk, I will discuss two projects in which we design and implement two novel properties that replication can achieve. With each property, we also define the set of tradeoffs introduced as well as propose new techniques for exploring these tradeoffs. Our work shows that replication has several more useful properties than previously assumed. First, I will discuss Replex, which harnesses distributed storage redundancy to build distributed secondary indices. Traditionally, storage systems punt on building fully functional distributed secondary indices because they do not have the correct primitive for doing so. We introduce a new replication primitive, a replex, that treats distributed secondary indices as first-class data objects. The tradeoff that results is between steady-state and failure performance, and we explore this tradeoff with a primitive we denote a hybrid replex. Second, I will discuss DIRECT, which is a set of principles for systematically leveraging storage redundancy to fix corruption errors in live production storage systems. Corruption errors are generally treated as device failures in today's storage systems, but we show that by fixing them online, we can extend the lifetime of flash devices by orders of magnitude. The tradeoff that results is between size of failure domain (and hence time to recovery) and ease of implementation. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 2

Shilpa Nadimpalli Kobren FPO TOMORROW Thursday, May 31, 2018 at 10:00am in CS402.
by Barbara A. Mooring 31 May '18

31 May '18

Shilpa Nadimpalli Kobren will present her FPO TOMORROW Thursday, May 31, 2018 at 10:00am in CS402. All are welcomed to attend. Committee members: Mona Singh (adviser), Barbara Engelhardt (examiner), Stanislav Shvartsman (examiner), Olga Troyanskaya (reader), and Benjamin J. Raphael (reader) Title: Detecting and Analyzing Variation in Protein Interactions Abstract: Proteins carry out a dazzling multitude of functions by interacting with DNA, RNA, other proteins and various other molecules within our cells. Together these interactions comprise complex networks that differ naturally across cells within an organism, across individuals in a population, and across species. Although such variation is critical for normal organismal functioning, mutations affecting protein interactions are also known to underlie a wide range of human diseases. In this dissertation, I introduce novel computational approaches that explore the extent to which specific protein interactions vary across species, across healthy individuals, and across individuals with cancer. To start, I focus on interaction variation across species. It is well established that changes in protein-DNA interactions underlie a wide range of observable differences across species. These differences are primarily thought to stem from changes in the DNA sites that transcription factor (TF) proteins bind to, although changes in the binding properties of TFs themselves have also been observed. Determining the prevalence of such TF changes, however, remains infeasible using current experimental approaches. Here, I develop and apply a comparative genomics framework to systematically quantify changes in the DNA-binding properties of orthologous TFs across species spanning ~45 million years of evolutionary divergence. I demonstrate that, contrary to expectation, cross-species regulatory network divergence resulting from changes in non-duplicated DNA-binding proteins is pervasive. These findings reveal a widespread yet largely unstudied source of divergence across transcriptional regulatory programs in animals. Next, I turn my attention to interaction variation across individuals. In order to comprehensively quantify this, I first combine large-scale sequence, domain and structure information to pinpoint sites within protein domains---the fundamental structural units in proteins---that are involved in binding DNA, RNA, peptides, ions, metabolites, or other small molecules. This domain-based approach enables us to identify putative interaction sites in over 60% of human genes, representing a 2.4-fold improvement over comparable state-of-the-art approaches for this task. I next demonstrate that whereas domain-inferred interaction sites are significantly depleted of natural variants across ~60,000 healthy individuals, these same sites are significantly enriched for cancer mutations across ~11,000 tumor samples. My analysis demonstrates that the cellular network variation that occurs across healthy individuals is unlikely to be due to changes within proteins; in contrast, mutations acquired in cancers appear to preferentially alter cellular networks by perturbing the proteins themselves. Finally, I show how we can leverage an interaction-based viewpoint to uncover mutated genes that play causal roles in human cancers. In particular, I aim to uncover genes whose interaction interfaces are significantly altered in tumors. Towards this end, I develop a robust computational framework that integrates my per-domain-position binding propensities with additional sources of biological data regarding protein functionality. I demonstrate that by analytically computing the significance of patterns of mutations, my approach is able to achieve a dramatic improvement in runtime over a typical empirical permutation test for this task. Moreover, my interaction-based method not only recapitulates known cancer driver genes faster and with greater precision than previous methods, but it also uncovers relatively rarely-mutated genes with likely roles in cancer. Through focusing on the somatic alteration of protein interaction interfaces in tumors, my method can inform the perturbed molecular mechanisms across known and putative cancer genes, thereby enabling valuable insights that may help guide personalized cancer treatments. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 1

Yi Zhang General Exam Presentation TODAY Tuesday, May 29, 2018 10:00 am CS 302
by Barbara A. Mooring 29 May '18

29 May '18

Yi Zhang General Exam Presentation TODAY Tuesday, May 29, 2018 10:00 am CS 302 Committee: Prof. Sanjeev Arora (advisor), Prof. Elad Hazan, Prof. Sebastian Seung Title: Theory and Practice of Generative Adversarial Networks (GANs) Abstract: I will discuss the (in)ability of GANs to learn the data generating distribution. A theoretical analysis of various GAN architectures will be presented, along with a principled and practical test for the support size of Generator’s distribution. In the first part of my talk, I'll show training of GAN architectures may appear successful but the trained distribution may be far from target distribution in standard metrics. The presented theory prophecies the notorious “mode collapse” failure mode of GANs. It is also shown that an approximate pure equilibrium exists in the discriminator/generator game for a special class of generators with natural training objectives when generator capacity and training set sizes are moderate. This existence of equilibrium inspires MIX+GAN protocol, which can be combined with any existing GAN training, and empirically shown to improve some of them. In the second part, I’ll extend the theoretical analysis to more recent encoder-decoder GANs architectures (e.g., BiGAN/ALI), which were proposed to learn more meaningful features via GANs and (consequently) to also solve the mode-collapse issue. Specifically, I’ll show that such encoder-decoder training objectives still cannot guarantee learning of the full distribution. More seriously, they cannot prevent learning meaningless codes for data, contrary to usual intuition. In addition, I’ll also propose a novel test for estimating support size using the birthday paradox of discrete probability. Using this, empirical evidence is presented that well-known GANs approaches do learn distributions of fairly low support. Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 0

Colloquium Speaker-Daniel Sanchez, TODAY at 12:30pm
by Emily C. Lawrence 29 May '18

29 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

Reminder: Colloquium Speaker-Daniel Sanchez, tomorrow at 12:30pm
by Emily C. Lawrence 28 May '18

28 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

Shilpa Nadimpalli Kobren FPO Thursday, May 31, 2018 at 10:00 am CS402
by Mike Freedman 25 May '18

25 May '18

Shilpa Nadimpalli Kobren will present her FPO on Thursday, May 31, 2018 at 10:00am in CS402. All are welcomed to attend. *Committee members:* Mona Singh (adviser), Barbara Engelhardt (examiner), Stanislav Shvartsman (examiner), Olga Troyanskaya (reader), and Benjamin J. Raphael (reader) *Title: *Detecting and Analyzing Variation in Protein Interactions *Abstract: * Proteins carry out a dazzling multitude of functions by interacting with DNA, RNA, other proteins and various other molecules within our cells. Together these interactions comprise complex networks that differ naturally across cells within an organism, across individuals in a population, and across species. Although such variation is critical for normal organismal functioning, mutations affecting protein interactions are also known to underlie a wide range of human diseases. In this dissertation, I introduce novel computational approaches that explore the extent to which specific protein interactions vary across species, across healthy individuals, and across individuals with cancer. To start, I focus on interaction variation across species. It is well established that changes in protein-DNA interactions underlie a wide range of observable differences across species. These differences are primarily thought to stem from changes in the DNA sites that transcription factor (TF) proteins bind to, although changes in the binding properties of TFs themselves have also been observed. Determining the prevalence of such TF changes, however, remains infeasible using current experimental approaches. Here, I develop and apply a comparative genomics framework to systematically quantify changes in the DNA-binding properties of orthologous TFs across species spanning ~45 million years of evolutionary divergence. I demonstrate that, contrary to expectation, cross-species regulatory network divergence resulting from changes in non-duplicated DNA-binding proteins is pervasive. These findings reveal a widespread yet largely unstudied source of divergence across transcriptional regulatory programs in animals. Next, I turn my attention to interaction variation across individuals. In order to comprehensively quantify this, I first combine large-scale sequence, domain and structure information to pinpoint sites within protein domains---the fundamental structural units in proteins---that are involved in binding DNA, RNA, peptides, ions, metabolites, or other small molecules. This domain-based approach enables us to identify putative interaction sites in over 60% of human genes, representing a 2.4-fold improvement over comparable state-of-the-art approaches for this task. I next demonstrate that whereas domain-inferred interaction sites are significantly depleted of natural variants across ~60,000 healthy individuals, these same sites are significantly enriched for cancer mutations across ~11,000 tumor samples. My analysis demonstrates that the cellular network variation that occurs across healthy individuals is unlikely to be due to changes within proteins; in contrast, mutations acquired in cancers appear to preferentially alter cellular networks by perturbing the proteins themselves. Finally, I show how we can leverage an interaction-based viewpoint to uncover mutated genes that play causal roles in human cancers. In particular, I aim to uncover genes whose interaction interfaces are significantly altered in tumors. Towards this end, I develop a robust computational framework that integrates my per-domain-position binding propensities with additional sources of biological data regarding protein functionality. I demonstrate that by analytically computing the significance of patterns of mutations, my approach is able to achieve a dramatic improvement in runtime over atypical empirical permutation test for this task. Moreover, my interaction-based method not only recapitulates known cancer driver genes faster and with greater precision than previous methods, but it also uncovers relatively rarely-mutated genes with likely roles in cancer. Through focusing on the somatic alteration of protein interaction interfaces in tumors, my method can inform the perturbed molecular mechanisms across known and putative cancer genes, thereby enabling valuable insights that may help guide personalized cancer treatments.

1 0

Wei Hu General Exam Presentation - Friday, May 25, 2018 1:00 pm CS331
by Barbara A. Mooring 25 May '18

25 May '18

Wei Hu will present his General Exam Presentation on Friday, May 25, 2018 at 1:00 pm in CS331. Committee: Sanjeev Arora (adviser), Elad Hazan, Yoram Singer Title: Advances in Convex and Non-Convex Approaches to Low-Rank Matrix Optimization Abstract: Low-rank matrix estimation is a fundamental class of problems that find a wide range of applications in machine learning. In this talk, I will present two recent results on the optimization side of such problems, one using a convex approach and another using a non-convex approach. Faster optimization over trace-norm balls Minimizing a convex matrix function over a trace-norm ball usually serves as a convex surrogate to low-rank matrix optimization. In this work, we propose a rank-k variant of the classical Frank-Wolfe algorithm to solve this problem. Our algorithm replaces the top singular vector computation (1-SVD) in Frank-Wolfe with a top-k singular vector computation (k-SVD), which can be done by repeatedly applying 1-SVD k times. Alternatively, our algorithm can be viewed as a rank-k restricted version of projected gradient descent. We show that our algorithm has a linear convergence rate when the objective function is smooth and strongly convex, and the optimal solution has rank at most k. This improves the convergence rate and the total time complexity of the Frank-Wolfe method and its variants. Implicit regularization of gradient descent on learning multi-layer homogeneous models We consider directly using gradient descent to solve the low-rank matrix factorization problem, i.e., minimizing ||UV-M||_F^2 over the two factors U and V simultaneously. This problem, together with many multi-layer models such as deep neural networks with ReLU activation, have the property of homogeneity. A direct consequence of homogeneity is that a solution can produce small function value while being unbounded, which poses significant difficulty in analyzing first-order optimization methods like (stochastic) gradient descent. In this work, we prove that for a large class of deep homogeneous models, gradient descent with infinitesimal step size effectively enforces the differences between the squared L2 norms across different layers to remain invariant, and thus different layers are automatically balanced. Inspired by this finding, we show that for matrix factorization, gradient descent with random initialization and positive step size converges to a bounded global minimum. The first result is joint work with Zeyuan Allen-Zhu (MSR), Elad Hazan (Princeton) and Yuanzhi Li (Princeton). The second result is joint work with Simon S. Du (CMU) and Jason D. Lee (USC). Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 2