- talks - lists.cs.princeton.edu

Simons Foundation Lecture: Prof. Mark Braverman, Friday May 14
by Emily C. Lawrence 06 May '21

06 May '21

Simons Foundation Lecture Speaker: Mark Braverman, Princeton University Title: Tiling Space and Making Hard Problems Harder Date: Friday, May 14, 2021 Time: 5:00 – 6:15 PM ET Talk + Q&A Register here: [ https://www.simonsfoundation.org/event/tiling-space-and-making-hard-problem… | https://www.simonsfoundation.org/event/tiling-space-and-making-hard-problem… ] Abstract: A shape can tile space if we can take infinitely many copies of the shape and shift them around to cover every point without overlapping. For example, squares and hexagons can tile a plane, but circles can’t. Questions linger, though. What is the smallest surface area a tile may have? Does the answer change if we require the tiles to be symmetric? In this lecture, Mark Braverman will discuss the question of minimizing the surface area of tiles, a problem that dates back to the 19th century. The question turns out to have surprising connections to computational complexity theory in the context of combining computationally difficult problems to make them even harder. Braverman will elucidate these connections and present results on the minimum surface area problem. Bio: Braverman is a professor at Princeton University. He works primarily on building new connections between theoretical computer science and other disciplines, including information theory, game theory, dynamical systems, analysis and geometry. He received a 2016 European Mathematical Society Prize and a 2019 NSF Alan T. Waterman Award.

1 0

Ariel Bronner will present his General Exam "An integer programming approach for learning Boolean models of cellular signalling and regulation" on Tuesday, May 11, 2021 at 11:30 AM via Zoom.
by Judith A. Farquer 04 May '21

04 May '21

Ariel Bronner will present his General Exam "An integer programming approach for learning Boolean models of cellular signalling and regulation” on Tuesday, May 11, 2021 at 11:30AM via Zoom. Zoom Link: [ https://princeton.zoom.us/j/9480668609 | https://princeton.zoom.us/j/9480668609 ] The members of Ariel’s committee are as follows: (Mona Singh (adviser), Olga Troyanskaya, and Ben Raphael Link to Abstract: [ https://docs.google.com/document/d/1LzZ6A8cOj7ESdCGhCFaG6wuR93J1YsTv2t4QAz0… | https://docs.google.com/document/d/1LzZ6A8cOj7ESdCGhCFaG6wuR93J1YsTv2t4QAz0… ] Link to Reading List: [ https://docs.google.com/document/d/1rEjBCtOvkOXKrF6ZSbdMfAULjSH2EYgXfTElmKq… | https://docs.google.com/document/d/1rEjBCtOvkOXKrF6ZSbdMfAULjSH2EYgXfTElmKq… ] Everyone is invited to attend the talk, and those faculty members wishing to remain for the oral exam following are welcome to do so.

1 0

Alexander Strzalkowski will present his General Exam "Specifying Variation in Single-Cell RNA Sequencing Data" on Thursday, May 13, 2021 at 2PM via Zoom.
by jfarquer＠cs.princeton.edu 03 May '21

03 May '21

Alexander Strzalkowski will present his General Exam " Specifying Variation in Single-Cell RNA Sequencing Data" on Thursday, May 13, 2021 at 2PM via Zoom. Zoom Link: https://princeton.zoom.us/j/95335607422 The members of his committee are as follows: Ben Raphael (adviser), Mona Singh, Josh Akey Link to Abstract and Reading List: https://docs.google.com/document/d/1hnIYSZcX81lGxOHi8433y4zyK8KFfe7vo7y0Scas 2nM/edit?usp=sharing Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.

1 0

Matheus Venturyne Xavier Ferreira will present his Pre-FPO "Economics and Computation in Decentralized Systems" on Wednesday, May 12, 2021 at 2pm via Zoom.
by jfarquer＠cs.princeton.edu 03 May '21

03 May '21

Matheus Venturyne Xavier Ferreira will present his Pre-FPO "Economics and Computation in Decentralized Systems" on Wednesday, May 12, 2021 at 2pm via Zoom. Zoom Link: https://princeton.zoom.us/j/94626343984 Committee: Examiners: S. Matthew Weinberg (adviser), Ran Raz, Arvind Narayanan Readers: Mark Braverman and David Parkes (Harvard University) All are welcome to attend. Title: Economics and Computation in Decentralized Systems Abstract: While algorithmic game theory studies algorithmic design under incentive constraints, computer security explores the protection of a computer system against adversaries. In one direction, economics provides new perspectives in designing secure computer systems because, in many real-world settings, adversaries are not intentionally malicious but rather rational and economically driven. Notably, Bitcoin has been successful in solving the permissionless Byzantine agreement by monetarily rewarding honest behavior. In the other direction, computer security provides new perspectives to mechanism design. Internet systems are increasingly less transparent and decentralized, which often challenges traditional assumptions from economics. Notably, internet auction lacks transparency, and in many practical instances, auctioneers cheat to improve revenue. In this talk, I will overview my research on designing incentive-compatible systems for an age where Internet systems are increasingly less transparent and decentralized. I will instantiate this agenda by presenting two projects. First, I will demonstrate how to implement incentive-compatible credible auctions where the auctioneer does not have incentive to cheat. I will highlight the connections between credible auction design with the problem of resource allocation on blockchains. Second, I will show that energy-efficient alternatives to proof-of-work blockchains can be ``almost'' as secure as proof-of-work when given access to public randomness by characterizing optimal strategies for the underlying infinite-state Markov decision process.

1 0

Kyle Genova will present his FPO "3D Representations for Learning to Reconstruct and Segment Shapes" on Friday, April 30, 2021 at 1PM via Zoom.
by jfarquer＠cs.princeton.edu 30 Apr '21

30 Apr '21

Kyle Genova will present his FPO "3D Representations for Learning to Reconstruct and Segment Shapes" on Friday, April 30, 2021 at 1PM via Zoom. Zoom link: <https://princeton.zoom.us/j/95639056934> https://princeton.zoom.us/j/95639056934 The members of Kyle's committee are as follows: Tom Funkhouser (adviser), Readers: Olga Russakovsky and Forrester Cole (Google), Examiners: Adam Finkelstein and Szymon Rusinkiewicz. A copy of his thesis is available upon request. Please email <mailto:gradinfo@cs.princeton.edu> gradinfo(a)cs.princeton.edu if you would like a copy of the thesis. Everyone is invited to attend his talk. Abstract follows below: The focus of this dissertation is the novel use of shape representations to empower 3D reasoning for reconstruction and segmentation. It is organized into three sections based on application: domain specific shape reconstruction (Chapter 2), general shape reconstruction (Chapter 3), and semantic segmentation (Chapter 4). In each chapter, we outline the setting and related work, and then introduce one or two approaches with a novel use of shape representation. Our key contribution is to use shape representation to enable new types of supervision and improve generalization when learning 3D priors. Because current reconstruction and segmentation methods share the use of learned 3D encoder and decoder architectures, these contributions apply to both tasks. In Chapters 2-4, we demonstrate experimentally that reconstruction and segmentation algorithms benefit from our choices of shape representation. A primary benefit of our approaches is enabling new types of supervision that require some property of the representation to be effective. Domain specific representation enables supervising 3D face reconstruction with a face recognition network for the first time, resulting in provably more recognizable reconstructions (Chapter 2). Our SIF representation learns shape correspondence from only reconstruction supervision (Chapter 3). Large, diverse image collections are already semantically labeled, making it possible to train 3D semantic segmentation models for datasets without point cloud annotations (Chapter 4). A secondary benefit is improved generalization by deriving better priors from existing supervision. We propose a new shape representation, LDIF, which is trained on existing 3D reconstruction data. LDIF learns robust local priors, improving generalization to unseen classes and shapes (Chapter 3). The addition of image-based supervision in segmentation algorithms improves generalization to cities with no 3D supervision (Chapter 4). We conclude that our choices of representation enable new supervision, better generalization, and learning useful 3D priors from readily available labels (e.g., labeled and unlabeled images, or unlabeled shape collections). We hypothesize that effective future representations will build on this trend by deriving higher level semantic priors from unannotated datasets and other inexpensive sources of supervision (Chapter 5).

2 1

Yi Zhang will present his Pre FPO "Advancing Deep Learning by Integrating Theory and Empirics" on Friday, April 30, 2021 at 2PM via Zoom.
by jfarquer＠cs.princeton.edu 30 Apr '21

30 Apr '21

Yi Zhang will present his Pre FPO "Advancing Deep Learning by Integrating Theory and Empirics" on Friday, April 30, 2021 at 2PM via Zoom. Zoom Link: https://us02web.zoom.us/j/6737994417?pwd=VUE2WWZXL1dTNDg1SWxFYjdyMGEvQT09 Committee: Examiners: Sanjeev Arora (advisor), Karthik Narasimhan, Jason D. Lee (ECE) Readers: Elad Hazan, Chi Jin (ECE) All are welcome to attend. Abstract: In sharp contrast to its remarkable empirical success stands a mathematical understanding of deep learning that is still in its infancy. Various puzzling behaviors of deep neural nets remain unexplained, and many widely deployed deep learning systems lack theoretical guarantees. This talk offers a perspective on the resemblance between deep learning research and natural sciences, especially modern physics at its formative stage where reciprocal interactions between theoretical and experimental studies fueled the growth. As the central object of study, deep neural networks are to deep learning as unknown particles are to physics. We can make significant progress by building theories inspired by empirical observations and verifying hypotheses with designed experiments. In this talk, I will present several of my representative works that follow this research philosophy. Firstly, I will introduce a finite-sample analysis of Generative Adversarial Networks that predicts the existence of degenerate solutions (i.e. mode collapse), which we confirm empirically using a principled test. Then I will present how the empirically identified 'noise stability' of deep neural networks trained on real-life data leads to a substantially stronger generalization measure for deep learning. Finally, I will describe our recent work on designing a simple test for measuring how much deep learning has overfitted to standard datasets.

1 0

CS Distinguished Colloquium Speaker: Jon Kleinberg, TODAY at 4:30pm
by Emily C. Lawrence 29 Apr '21

29 Apr '21

CS Distinguished Colloquium Speaker Jon Kleinberg, Cornell University Host: Sanjeev Arora Date: Thursday, April 29 Time: 4:30pm ET Event page: [ https://www.cs.princeton.edu/events/26075 | https://www.cs.princeton.edu/events/26075 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_lh8warWtSVexsnJqz3tsHA | https://princeton.zoom.us/webinar/register/WN_lh8warWtSVexsnJqz3tsHA ] Title: Monoculture and Simplicity in an Ecosystem of Algorithmic Decision-Making Abstract: Algorithms are increasingly used to aid decision-making in high-stakes settings including employment, lending, healthcare, and the legal system. This development has led to an ecosystem of growing complexity in which algorithms and people interact around consequential decisions, often mediated by organizations and firms that may be in competition with one another. We consider two related sets of issues that arise in this setting. First, concerns have been raised about the effects of algorithmic monoculture, in which multiple decision-makers all rely on the same algorithm. In a set of models drawing on minimal assumptions, we show that when competing decision-makers converge on the use of the same algorithm as part of a decision pipeline, the result can potentially be harmful for social welfare even when the algorithm is more accurate than any decision-maker acting on their own. Second, we consider some of the canonical ways in which data is simplified over the course of these decision-making pipelines, showing how this process of simplification can introduce sources of bias in ways that connect to principles from the psychology of stereotype formation. The talk will be based on joint work with Sendhil Mullainathan and Manish Raghavan. Bio: Jon Kleinberg is the Tisch University Professor in the Departments of Computer Science and Information Science at Cornell University. His research focuses on the interaction of algorithms and networks, the roles they play in large-scale social and information systems, and their broader societal implications. He is a member of the National Academy of Sciences and the National Academy of Engineering, and the recipient of MacArthur, Packard, Simons, Sloan, and Vannevar Bush research fellowships, as well awards including the Harvey Prize, the Nevanlinna Prize, and the ACM Prize in Computing.

1 0

Zexuan Zhong will present his General Exam "Extracting Knowledge from Text and Pre-trained Language Models" on Tuesday, May 4, 2021 at 1:30PM via Zoom.
by jfarquer＠cs.princeton.edu 28 Apr '21

28 Apr '21

Zexuan Zhong will present his General Exam "Extracting Knowledge from Text and Pre-trained Language Models" on Tuesday, May 4, 2021 at 1:30PM via Zoom. Zoom Link: https://princeton.zoom.us/j/93687632836 The members of Zexuan's committee are as follows: Danqi Chen (adviser), Karthik Narasimhan, Sanjeev Arora Link to Abstract: https://docs.google.com/document/d/1HhfSSWiceWWs4hhP2ZfX0lD2fpfVC6qj7_zZPE4y 3XY/edit?usp=sharing Link to Reading List: https://docs.google.com/document/d/16Xn7Z9s8nniZASZlgcZbl6QQrYeP_DPucNywVw7l 8QY/edit?usp=sharing Everyone is invited to attend the talk, and those faculty wishing to remain for the oral exam following are welcome to do so.

1 0

Reminder: CS Distinguished Colloquium Speaker: Jon Kleinberg, tomorrow at 4:30pm
by Emily C. Lawrence 28 Apr '21

28 Apr '21

CS Distinguished Colloquium Speaker Jon Kleinberg, Cornell University Host: Sanjeev Arora Date: Thursday, April 29 Time: 4:30pm ET Event page: [ https://www.cs.princeton.edu/events/26075 | https://www.cs.princeton.edu/events/26075 ] Register for Zoom webinar here: [ https://princeton.zoom.us/webinar/register/WN_lh8warWtSVexsnJqz3tsHA | https://princeton.zoom.us/webinar/register/WN_lh8warWtSVexsnJqz3tsHA ] Title: Monoculture and Simplicity in an Ecosystem of Algorithmic Decision-Making Abstract: Algorithms are increasingly used to aid decision-making in high-stakes settings including employment, lending, healthcare, and the legal system. This development has led to an ecosystem of growing complexity in which algorithms and people interact around consequential decisions, often mediated by organizations and firms that may be in competition with one another. We consider two related sets of issues that arise in this setting. First, concerns have been raised about the effects of algorithmic monoculture, in which multiple decision-makers all rely on the same algorithm. In a set of models drawing on minimal assumptions, we show that when competing decision-makers converge on the use of the same algorithm as part of a decision pipeline, the result can potentially be harmful for social welfare even when the algorithm is more accurate than any decision-maker acting on their own. Second, we consider some of the canonical ways in which data is simplified over the course of these decision-making pipelines, showing how this process of simplification can introduce sources of bias in ways that connect to principles from the psychology of stereotype formation. The talk will be based on joint work with Sendhil Mullainathan and Manish Raghavan. Bio: Jon Kleinberg is the Tisch University Professor in the Departments of Computer Science and Information Science at Cornell University. His research focuses on the interaction of algorithms and networks, the roles they play in large-scale social and information systems, and their broader societal implications. He is a member of the National Academy of Sciences and the National Academy of Engineering, and the recipient of MacArthur, Packard, Simons, Sloan, and Vannevar Bush research fellowships, as well awards including the Harvey Prize, the Nevanlinna Prize, and the ACM Prize in Computing.

1 0

Lucas Salvador will present his MSE Talk ":Demystifying the GPU Stall Cycle: Evaluating the Diagnosis of GPU Bottlenecks" on Wednesday 4/28/2021 at 2PM via Zoom.
by GRADINFO 26 Apr '21

26 Apr '21

Lucas Salvador will present his MSE Talk " Demystifying the GPU Stall Cycle: Evaluating the Diagnosis of GPU Bottlenecks" on Wednesday 4/28/2021 at 2PM via Zoom. Zoom Link: [ https://princeton.zoom.us/j/96305827497 | https://princeton.zoom.us/j/96305827497 ] Committee: David August (Adviser), Mohammad Shahrad (Reader) All are welcome to attend. Abstract: Graphics Processing Units (GPUs) have become ubiquitous in all modern intensive computing environments, having transitioned from their early use in Graphics to a plethora of other general compute applications. These tasks are all equally demanding, yet their distinct access patterns generate specific strains in the GPU hardware that evidence different bottlenecks. In order to extract the maximum performance possible from a GPU, application designers and architecture engineers typically have to work back from the symptoms, relying in a series of "rules of thumb" and abstract tools to distill insights that may or may not be related to the actual application bottlenecks. This has led to a series of techniques that have attempted, through the use of detailed simulation, to isolate the cause of bottlenecks in GPU devices. These approaches rely on a hierarchy of stall causes that attributes different importance to specific bottlenecks in the GPU pipeline. In this work, we evaluate the validity of these hierarchical approaches by comparing their insights with the results we could expect from a "perfect" GPU, that is, a simulation (run on GPGPU-Sim) where each specific bottleneck is fully removed, one at a time. By comparing the results across a series of benchmarks, we expose the limitations of these approaches, indicating how the flawed insights may result in misguided optimization. We then further discuss the conceptual pitfalls that seem to be responsible for these discrepancies, and use these to outline a series of desired properties we would expect from a successful diagnosis technique.

1 0