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

Colloquium Speaker-Bo Wang, Friday, April 27
by Emily C. Lawrence 20 Apr '18

20 Apr '18

Bo Wang, Stanford University Friday, April 27, 2018 - 12:30pm Computer Science - Room 105 Host: Mona Singh "Machine Learning Algorithms for Exploiting Spectral Structures of Biological Networks" Networks are ubiquitous in biology where they encode connectivity patterns at all scales of organization, from populations to a single cell. How to extract and understand non-trivial topological features and structures inherent in the networks is critical to understanding interactions within complicated biological systems. In this talk, I will introduce recent developments of machine learning algorithms that exploit spectral structures of networks for a wide range of biological applications, ranging from single-cell analysis to function prediction on protein-protein interaction networks. Specifically, I will first present a new method named SIMLR, combining both low-rank spectral regularization and multiple-kernel learning, to construct cell networks for sparse noisy single-cell RNA- seq data. The learned cell networks will enable effective dimension reduction, clustering and visualization. Second, I will discuss a novel method, Network Enhancement (NE), that aims to de-noise complex networks such as protein-protein interaction networks without corrupting spectral structures of the networks, therefore improving function prediction accuracy. Last, I will also briefly introduce recent advances where deep convolutional neural network is applied on biological networks (e.g., drug-target network) as a first-order spectral approximation of network structures. Bio: Bo Wang is a recent PhD graduate in Computer Science at Stanford University, an IEEE and CVF Fellow and an NSF Graduate Research Fellow. His research focuses on machine learning (particularly deep learning) on many applications in computer vision (e.g., image segmentation, object detection) and computational biology (e.g., single-cell analysis, integrative cancer subtyping). Prior to Stanford, he received his master degree at University of Toronto, majoring in numerical analysis.

1 0

Colloquium Speaker-Umesh Vazirani, Monday, April 23
by Emily Lawrence 19 Apr '18

19 Apr '18

Umesh Vazirani from UC Berkeley Monday, April 23, 2018 - 12:30pm Computer Science - Room 105 Host: Sanjeev Arora "Quantum Supremacy" and the Complexity of Random Circuit Sampling A critical goal for the field of quantum computation is quantum supremacy -- a demonstration of any quantum computation that is prohibitively hard for classical computers. Besides dispelling any skepticism about the viability of quantum computers, quantum supremacy also provides a test of quantum theory in the realm of high complexity. A leading near-term candidate, put forth by the Google/UCSB team, is sampling from the probability distributions of randomly chosen quantum circuits, called Random Circuit Sampling (RCS). While RCS was defined with experimental realization in mind (the first results are expected later this year), we give the first complexity-theoretic evidence of classical hardness of RCS, placing it on par with the best theoretical proposals for supremacy. Specifically, we show that RCS satisfies an average-case hardness condition -- computing output probabilities of typical quantum circuits is as hard as computing them in the worst-case, and therefore #P-hard. Our reduction exploits the polynomial structure in the output amplitudes of random quantum circuits, enabled by the Feynman path integral. We also describe a new verification measure which in some formal sense maximizes the information gained from experimental samples. Based on joint work with Adam Bouland, Bill Fefferman and Chinmay Nirkhe.

1 0

Colloquium Speaker-Taesoo Kim, TODAY at 12:30
by Emily C. Lawrence 19 Apr '18

19 Apr '18

Taesoo Kim from Georgia Institute of Technology Thursday, April 19, 2018 - 12:30pm Computer Science - Room 105 Host: Arvind Narayanan “Scaling Security Practices: Automated Approaches to Eliminate Security Vulnerabilities” Computer systems are highly vulnerable; attackers everyday discover new security vulnerabilities and exploit them to compromise the target systems. This talk will present our approaches to automatically prevent software vulnerabilities from exploitation. In particular, this talk will describe in detail two classes of vulnerabilities: an emerging class, called "type confusion" (or "bad casting"), that are commonly seen in modern web browsers, and a new class that we discovered, called "uninitialized padding," causing information leakage in the Linux kernel. This talk will explain what these vulnerabilities are, how attackers exploit them, why/how developers introduced them, and why it is non-trivial to avoid them in complex, real-world programs. Finally, our approaches to automatically eliminate them in practice will be demonstrated. Bio: Taesoo Kim is a Catherine M. and James E. Allchin Early Career Assistant Professor in the School Computer Science at the Georgia Institute of Technology (Georgia Tech). He also serves as the director of the Georgia Tech Systems Software and Security Center (GTS3). He is genuinely interested in building a system that prioritizes security principles first and foremost. Those principles include the total design of the system, analysis of its implementation, elimination of certain classes of vulnerabilities, and clear separation of its trusted components. His thesis work, in particular, focused on detecting and recovering from attacks on computer systems, known as "undo computing." Taesoo holds a S.M. (2011) and a Ph.D. (2014) from MIT.

1 0

Ben Lee, May 1 at 4:30
by Emily Lawrence 18 Apr '18

18 Apr '18

Ben Lee, Duke University May 1, 2018 at 4:30 p.m. Maeder Hall auditorium Title: Datacenters and Energy Efficiency: A Game-Theoretic Perspective Abstract: Sharing datacenter hardware improves energy efficiency, but whether strategic users participate in consolidated systems depends on management policies. Users who dislike allocations may refuse to participate and deploy private, less-efficient systems. We rethink systems management, drawing on game theory to model strategic behavior and incentivize participation. We illustrate this perspective for two fundamental challenges in datacenters. For power delivery, we design sprinting games to produce equilibria in which users selfishly draw power for performance boosts yet avoid oversubscribing the shared supply. For resource allocation, we use Cobb-Douglas utility functions to produce fair allocations that incentivize users to share cache and memory. These solutions provide foundations for rigorously managing systems shared by strategic, competitive participants. Biography: Benjamin Lee is an Associate Professor of Electrical and Computer Engineering at Duke University. He received his B.S. from the University of California at Berkeley (2004), his Ph.D. from Harvard University (2008), and his post-doctorate from Stanford University (2010). He has held visiting positions at Microsoft Research, Intel Labs, and Lawrence Livermore National Lab. Dr. Lee’s research interests include computer architecture, energy efficiency, and security / privacy. He pursues these interests by building interdisciplinary links to statistical inference and algorithmic economics. His research has been recognized by IEEE Micro Top Picks (4x), Communications of the ACM Research Highlights (3x), as well as paper honors from the ASPLOS, HPCA, MICRO, and SC conferences. He received the NSF Computing Innovation Fellowship, NSF CAREER Award, and Google Faculty Research Award.

1 0

NOTICE NEW TIME AND ROOM Jonathan Schneider will present his PreFPO Thursday, April 19, 2018 at 10:00 am in CS402
by Barbara A. Mooring 18 Apr '18

18 Apr '18

Jonathan Schneider will present his PreFPO Thursday, April 19, 2018 at 10:00 am in CS402 The members of his committee are as follows: Mark Braverman - Adviser, Matt Weinberg,Bernard Chazelle, Elad Hazan and Omri Weinstein(Columbia) All are welcomed to attend. Title: "Learning Algorithms in Strategic Environments" Abstract: Learning algorithms are often analyzed under the assumption their inputs are drawn from stochastic or adversarial sources. Increasingly, these algorithms are being applied in strategic settings, where we can hope for stronger guarantees. My research aims to understand the performance of existing learning algorithms in these settings, and to design new algorithms that perform well in these settings. In the first part of the talk, I will discuss the problem of repeatedly auctioning off an item to a single low-regret buyer. We will show that if the buyer uses classical low-regret learning algorithms such as EXP3 or Multiplicative Weights, it is possible for the seller to extract the full welfare of the buyer; on the other hand, we present a new low-regret learning algorithm for the buyer which guarantees that the seller receives no more than Myerson revenue (the best they can achieve by offering the same price every round). In the second part of the talk, I will discuss the problem of "contextual search", a contextual, multidimensional generalization of binary search. We will use tools from integral geometry (namely, the notion of "intrinsic volumes") to design an algorithm which obtains constant regret bounds for this problem. We then apply these techniques to the problem of dynamic pricing, where we achieve a tight regret bound of O(log log T) (improving exponentially on the best existing algorithm which achieved O(log T) regret). Barbara A. Mooring Interim Graduate Coordinator Computer Science Department Princeton University

1 0

Reminder: Colloquium Speaker-Taesoo Kim, tomorrow at 12:30
by Emily C. Lawrence 18 Apr '18

18 Apr '18

Taesoo Kim from Georgia Institute of Technology Thursday, April 19, 2018 - 12:30pm Computer Science - Room 105 Host: Arvind Narayanan “Scaling Security Practices: Automated Approaches to Eliminate Security Vulnerabilities” Computer systems are highly vulnerable; attackers everyday discover new security vulnerabilities and exploit them to compromise the target systems. This talk will present our approaches to automatically prevent software vulnerabilities from exploitation. In particular, this talk will describe in detail two classes of vulnerabilities: an emerging class, called "type confusion" (or "bad casting"), that are commonly seen in modern web browsers, and a new class that we discovered, called "uninitialized padding," causing information leakage in the Linux kernel. This talk will explain what these vulnerabilities are, how attackers exploit them, why/how developers introduced them, and why it is non-trivial to avoid them in complex, real-world programs. Finally, our approaches to automatically eliminate them in practice will be demonstrated. Bio: Taesoo Kim is a Catherine M. and James E. Allchin Early Career Assistant Professor in the School Computer Science at the Georgia Institute of Technology (Georgia Tech). He also serves as the director of the Georgia Tech Systems Software and Security Center (GTS3). He is genuinely interested in building a system that prioritizes security principles first and foremost. Those principles include the total design of the system, analysis of its implementation, elimination of certain classes of vulnerabilities, and clear separation of its trusted components. His thesis work, in particular, focused on detecting and recovering from attacks on computer systems, known as "undo computing." Taesoo holds a S.M. (2011) and a Ph.D. (2014) from MIT.

1 0

ORFE Colloquium: Tim Roughgarden, TODAY at 5pm in Sherrerd Hall 101
by Emily Lawrence 17 Apr '18

17 Apr '18

===== TODAY: ORFE Department Colloquium Announcement===== DATE: Tuesday, April 17, 2018 TIME: 5pm LOCATION: Sherrerd Hall 101 SPEAKER: Tim Roughgarden, Stanford University Title: How Computer Science Informs Modern Auction Design Abstract: Over the last twenty years, computer science has relied on concepts borrowed from game theory and economics to reason about applications ranging from internet routing to real-time auctions for online advertising. More recently, ideas have increasingly flowed in the opposite direction, with concepts and techniques from computer science beginning to influence economic theory and practice. In this lecture, Tim Roughgarden will illustrate this point with a detailed case study of the 2016-2017 Federal Communications Commission incentive auction for repurposing wireless spectrum. Computer science techniques, ranging from algorithms for NP-hard problems to nondeterministic communication complexity, have played a critical role both in the design of the reverse auction (with the government procuring existing licenses from television broadcasters) and in the analysis of the forward auction (when the procured licenses sell to the highest bidder). _____ Bio: Roughgarden is a professor of computer science and, by courtesy, management science and engineering at Stanford University. He joined the Stanford faculty in 2004, following a Ph.D. at Cornell University and a postdoc at the University of California, Berkeley. His research interests include the many connections between computer science and economics as well as the design, analysis, applications and limitations of algorithms. He has received the ACM Grace Murray Hopper Award, the Presidential Early Career Award for Scientists and Engineers (PECASE), the Kalai Prize in Computer Science and Game Theory, the Social Choice and Welfare Prize, the Mathematical Programming Societys Tucker Prize, and the EATCS-SIGACT Gödel Prize. His books include Twenty Lectures on Algorithmic Game Theory (2016) and Algorithms Illuminated (2017).

1 0

Colloquium Speaker-Joy Arulraj, TODAY at 12:30
by Emily C. Lawrence 17 Apr '18

17 Apr '18

Joy Arulraj from Carnegie Mellon University Tuesday, April 17, 2018 - 12:30pm Computer Science - Room 105 Host: Wyatt Lloyd “Data Management on Non-Volatile Memory” We are at an exciting point in the evolution of memory technology. Device manufacturers have created a new non-volatile memory (NVM) technology that can serve as both system memory and storage. NVM supports fast reads and writes similar to volatile memory, but all writes to it are persistent like a solid-state disk. The advent of NVM invalidates decades of design decisions that are deeply embedded in today's database management systems (DBMSs). These systems are unable to take full advantage of NVM because their internal architectures are predicated on the assumption that memory is volatile. With NVM, many of the components of today's DBMSs are unnecessary and will degrade the performance of data-intensive applications. Thus, the best way to resolve these shortcomings is by designing a new system explicitly tailored for NVM. In this talk, I will present my research on the design and development of an NVM DBMS, called Peloton. Peloton's architecture shows that the impact of NVM spans across all the layers of the DBMS. I will first introduce write-behind logging, an NVM-centric protocol that improves the availability of the database system by two orders-of-magnitude compared to the widely-used write-ahead logging protocol. I will then present the BzTree , an NVM-centric index data structure that illustrates how to simplify programming on NVM. In drawing broader lessons from this work, I will argue that all types of software systems, including file systems, machine-learning systems, and key-value stores, are amenable to similar architectural changes to achieve high performance and availability on NVM. Bio: Joy Arulraj is a Ph.D. candidate at Carnegie Mellon University. His research interests are in database systems and data science. As part of his dissertation work, he has studied and built the first non-volatile memory database system, called Peloton, for performing large-scale transaction processing and real-time data analytics. He is the recipient of the Carnegie Mellon Presidential Fellowship and a Samsung Ph.D. Fellowship.

1 0

Reminder: Colloquium Speaker-Joy Arulraj, tomorrow at 12:30
by Emily C. Lawrence 16 Apr '18

16 Apr '18

Joy Arulraj from Carnegie Mellon University Tuesday, April 17, 2018 - 12:30pm Computer Science - Room 105 Host: Wyatt Lloyd “Data Management on Non-Volatile Memory” We are at an exciting point in the evolution of memory technology. Device manufacturers have created a new non-volatile memory (NVM) technology that can serve as both system memory and storage. NVM supports fast reads and writes similar to volatile memory, but all writes to it are persistent like a solid-state disk. The advent of NVM invalidates decades of design decisions that are deeply embedded in today's database management systems (DBMSs). These systems are unable to take full advantage of NVM because their internal architectures are predicated on the assumption that memory is volatile. With NVM, many of the components of today's DBMSs are unnecessary and will degrade the performance of data-intensive applications. Thus, the best way to resolve these shortcomings is by designing a new system explicitly tailored for NVM. In this talk, I will present my research on the design and development of an NVM DBMS, called Peloton. Peloton's architecture shows that the impact of NVM spans across all the layers of the DBMS. I will first introduce write-behind logging, an NVM-centric protocol that improves the availability of the database system by two orders-of-magnitude compared to the widely-used write-ahead logging protocol. I will then present the BzTree , an NVM-centric index data structure that illustrates how to simplify programming on NVM. In drawing broader lessons from this work, I will argue that all types of software systems, including file systems, machine-learning systems, and key-value stores, are amenable to similar architectural changes to achieve high performance and availability on NVM. Bio: Joy Arulraj is a Ph.D. candidate at Carnegie Mellon University. His research interests are in database systems and data science. As part of his dissertation work, he has studied and built the first non-volatile memory database system, called Peloton, for performing large-scale transaction processing and real-time data analytics. He is the recipient of the Carnegie Mellon Presidential Fellowship and a Samsung Ph.D. Fellowship.

1 0

Colloquium Speaker-Jacob Andreas, TODAY at 12:30
by Emily C. Lawrence 16 Apr '18

16 Apr '18

Jacob Andreas from University of California at Berkeley Monday, April 16, 2018 - 12:30pm Computer Science - Room 105 Host: Sanjeev Arora “Learning from Language” Natural language is built from a library of concepts and compositional operators that provide a rich source of information about how humans understand the world. Can this information help us build better machine learning models? In this talk, we'll explore three ways of integrating compositional linguistic structure and learning: using language as a source of modular reasoning operators for question answering, as a scaffold for fast and generalizable reinforcement learning, and as a tool for understanding representations in neural networks. Bio: Jacob Andreas is a fifth-year PhD student at UC Berkeley working in natural language processing. He holds a B.S. from Columbia and an M.Phil. from Cambridge, where he studied as a Churchill scholar. His papers were recognized at NAACL 2016 and ICML 2017. Jacob has been an NSF graduate fellow, a Huawei--Berkeley AI fellow, and a Facebook fellow.

1 0