December 2020 - talks - lists.cs.princeton.edu

Nick Turner will present his Pre-FPO "Connectivity inference for petascale neural circuit reconstruction" on Tuesday, December 22, 2020 at 3pm via Zoom.
by Nicki Mahler 21 Dec '20

21 Dec '20

Nick Turner will present his Pre-FPO "Connectivity inference for petascale neural circuit reconstruction" on Tuesday, December 22, 2020 at 3pm via Zoom. Zoom link: https://princeton.zoom.us/j/99102493411?pwd=MUxNTEY3U0ZaZ1V4MDl6ZDFKZmpydz09 The members of his committee are as follows: Examiners : H. Sebastian Seung (advisor), Barbara Engelhardt, Olga Russakovsky Readers: H. Sebastian Seung, R. Clay Reid (Allen Institute for Brain Sciences), Andreas Tolias (Baylor College of Medicine & Rice University) Abstract: Reconstructing neural circuitry has the potential to reveal fundamental principles of brain function and intelligence. This work attempts to improve neural circuit reconstruction from electron microscopy (EM), study the resulting data, and release these data to the public for further study. A major result of this work is the implementation of an automated system for inferring the connectivity between neurons within large scale EM image volumes. This system was used to detect over 300 million synapses in the largest connectivity map extracted using EM to date. These results were also judged to be highly accurate by a team of independent evaluators. A separate major goal of this work has been the public release of EM reconstructions for study by the scientific community after performing our own computational analyses to illustrate their utility. As one example, we combine the connectivity inference techniques above with an automated reconstruction of neuronal mitochondria to analyze the relationship between input synaptic density and mitochondrial density. The final chapter will explore an automated system to detect the errors of automated circuit reconstruction within large EM image volumes. In this presentation, I will review all of the work summarized above and consider potential paths forward on this final task.

1 2

Raghuvansh Saxena will present his Pre FPO "Communication Complexity: For Coding, Commerce, and Currents" on Wednesday, December 23, 2020 at 3pm via Zoom.
by Nicki Mahler 18 Dec '20

18 Dec '20

Raghuvansh Saxena will present his Pre FPO " Communication Complexity: For Coding, Commerce, and Currents" on Wednesday, December 23, 2020 at 3pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/98882731404 | https://princeton.zoom.us/j/98882731404 ] The members of his committee are as follows: Examiners: Gillat Kol (adviser), Bernard Chazelle, and Ran Raz Readers: Mark Braverman, Matt Weinberg Abstract: Communication complexity is the study of how two or more parties with private inputs compute a function that depends on all their inputs. The scarce resource is communication, or the number of bits exchanged between the parties. Communication complexity naturally applies to settings with interaction between multiple parties, such as auction design and distributed computing. Surprisingly, it also applies to many superficially unrelated settings, such as streaming algorithms and data structures, as bounds on communication can often be translated into bounds on other resources of interest, such as the memory required by a streaming algorithm. Much of the work in this dissertation is in the area of interactive coding, which studies communication complexity in the presence of noise. I describe my research in both two party interactive coding, where my work not only shows protocols resilient to a larger fraction of noise than the previous state-of-the-art, but also provides matching impossibility results ruling out protocols with higher noise resilience, and in multi-party interactive coding, where I give tight bounds for codes for several emergent distributed models, including the broadcast model, the radio network model, and the beeping model. Another large part is dedicated to communication problems in auction design theory, where the participating parties have their own interests and may not follow the protocol unless incentivized to do so. A common theme of this part is establishing tight separations between different classes of auctions, and understanding how various aspects of an auction affect its communication complexity. These separations are shown for both welfare maximizing and revenue maximizing auctions, and are often the first quantitative separations to be shown for these problems. Finally, I cover my work showing tight bounds on the memory requirement of streaming algorithms by analyzing the induced low-round communication protocols. These bounds are the first of their kind as they apply to algorithms that can take multiple passes over the input. They are also extremely general, and hold for a large class of natural streaming problems.

1 0

Prakash Murali will present his Pre FPO "Enabling Practical Quantum Computation: Compiler and Architecture Techniques for Bridging the Algorithms-to-Devices Resource Gap" on Thursday, December 17, 2020 at 9am via Zoom.
by Nicki Mahler 14 Dec '20

14 Dec '20

Prakash Murali will present his Pre FPO "Enabling Practical Quantum Computation: Compiler and Architecture Techniques for Bridging the Algorithms-to-Devices Resource Gap" on Thursday, December 17, 2020 at 9am via Zoom. Zoom link: [ https://princeton.zoom.us/j/95808315646 | https://princeton.zoom.us/j/95808315646 ] Committee: Margaret Martonosi (Advisor, Reader, Examiner); Readers: Kyle Jamieson and Fred Chong (University of Chicago); Examiners: Andrew Houck (Princeton EE), Nathalie de Leon (Princeton EE) Title: Enabling Practical Quantum Computation: Compiler and Architecture Techniques for Bridging the Algorithms-to-Devices Resource Gap Abstract: Quantum computing (QC) is a radically new paradigm which is poised to impact diverse fields such as cryptography, chemistry and machine learning. In recent years, QC hardware has progressed considerably with small systems being prototyped by industry and academic vendors. However, there is a huge gap between the resource requirements of promising applications and the hardware that is buildable now; qubit counts and operational noise constraints of applications exceed hardware capabilities by 5-6 orders of magnitude. My thesis seeks to enable practical QC by bridging this gap: from the top with novel compiler techniques to optimize application requirements and from the bottom via system architectures efficiently exploiting scarce QC resources. Towards bridging the gap from the top, my thesis proposes two techniques: noise adaptive compilation to adapt application executables to the variable noise characteristics of QC devices and software approaches for mitigating crosstalk errors which occur during parallel gate operations. On real QC executions, we demonstrate average fidelity improvements of 3X using noise-adaptivity and 2X using crosstalk mitigation, compared to state-of-the-art techniques. Towards closing the gap from the bottom, my work includes extensive architectural analysis for current superconducting and trapped ion-based QC systems and hardware-software co-design techniques to improve the fidelity of next-generation trapped ion systems. In response to my work, several industry vendors have included noise-adaptivity and its extensions as part of their toolflows and adjusted device architecture to expose more native operations and hardware characterization data.

1 0

Karan Singh will present his Pre FPO "The Nonstochastic Control Problem" on Monday, December 14, 2020 at 11am via Zoom.
by Nicki Mahler 10 Dec '20

10 Dec '20

Karan Singh will present his Pre FPO "The Nonstochastic Control Problem" on Monday, December 14, 2020 at 11am via Zoom. Zoom link: [ https://princeton.zoom.us/j/96758411857 | https://princeton.zoom.us/j/96758411857 ] The members of his committee are as follows: Examiners: Elad Hazan (advisor), Sanjeev Arora, Anirudha Majumdar (MAE) Readers: Karthik Narasimhan, Sham Kakade (University of Washington) Title: The Nonstochastic Control Problem Abstract: Control in dynamical systems is a fundamental problem, with wide-reaching applications in autonomous systems, engineering, and sciences. This thesis outlines algorithms and their analyses for feedback-driven learning that make progress on several fronts: robustness, adaptivity, generality, and sample efficiency. The focal point of this thesis is the introduction of the nonstochastic control framework, which builds an algorithmic (against the traditionally analytic) foundation for control theory. This segment provides robust algorithmic primitives for basic control subroutines. Concretely, it presents: An efficient algorithm for controlling linear systems in the presence of nonstochastic perturbations with an instance-optimal regret guarantee. Beyond the realm of both robust and stochastic control, such a data-driven notion of optimality offers worst-case guarantees with a promise of exceptional performance on benign problem instances; The first logarithmic regret result for the classical tracking problem, using optimization-based tools that go beyond dynamic programming based approaches; Extensions of the above to unknown and partially observed systems. The second part of the thesis addresses the challenge of learning to act in non-stationary environments given a handful of trials, a version of the sim-to-real challenge. It provides a provable algorithm that negotiates this challenge using the algorithmic foundation delineated above, and demonstrates its efficacy over known approaches in non-linear settings. The final segment concerns the generalization of the notion of feedback in interactive learning beyond scalar rewards. It provides an efficient reductions-based approach to tackling concave reward functionals, that may increasingly be found in underlying exploration subroutines. This is accomplished via a novel generalization of classical boosting and gradient boosting to the online convex optimization setting.

1 0

Sotirios Apostolakis will present his FPO "A Sensible Approach to Speculative Automatic Parallelization" on Wednesday, December 9, 2020 at 2pm via Zoom.
by Nicki Mahler 07 Dec '20

07 Dec '20

Sotirios Apostolakis will present his FPO "A Sensible Approach to Speculative Automatic Parallelization" on Wednesday, December 9, 2020 at 2pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/97706523775 | https://princeton.zoom.us/j/97706523775 ] The members of his committee are as follows: Examiners: Davis August (adviser), Brian Kernighan, and Andrew Appel; Readers: Zachary Kincaid and Simone Campanoni (Northwestern University) A copy of his thesis is available upon request. Please email ngotsis(a)cs.princeton if you would like a copy of the thesis. Everyone is invited to attend the talk. Abstract: The promise of automatic parallelization, freeing programmers from the error-prone and time-consuming process of making efficient use of parallel processing resources, remains unrealized. For decades, the imprecision of memory analysis limited the applicability of automatic parallelization. The introduction of speculation to automatic parallelization overcame these applicability limitations but caused profitability problems due to high communication and bookkeeping costs for speculation validation and commit. This dissertation shifts the focus from applicability to profitability by making speculative automatic parallelization more efficient. Unlike current approaches that perform analysis and transformations independently and in sequence, the proposed system integrates, without loss of modularity, memory analysis, speculative techniques, and enabling transformations. Specifically, this dissertation involves three main contributions. First, it introduces a novel speculation-aware collaborative analysis framework (SCAF) that minimizes the need for high-overhead speculation. Second, it proposes a new parallelizing-compiler design that enables careful planning. Third, it presents new efficient speculative privatization transformations that avoid privatization overheads of prior work. SCAF learns of available speculative information via profiling, computes its full impact on memory dependence analysis, and makes this resulting information available for all code optimizations. SCAF is modular (adding new analysis modules is easy) and collaborative (modules cooperate to produce a result more precise than the confluence of all individual results). Relative to the best prior speculation-aware dependence analysis technique, SCAF dramatically reduces the need for expensive-to-validate memory speculation in the hot loops of all 16 evaluated C/C++ SPEC benchmarks. The introduction of planning in the compiler enables the selection of parallelizationenabling transformations based on their cost and overall impacts. The benefit is twofold. First, the compiler only applies a minimal-cost set of enabling transformations. Second, this decision-making process makes the addition of new efficient speculative enablers possible, including the proposed privatization transformations. This dissertation integrates these contributions into a fully-automatic speculativeDOALL parallelization framework for commodity hardware. By reducing speculative parallelization overheads in ways not possible with prior parallelization systems, this work obtains higher overall program speedup (23.0⇥ for 12 general-purpose C/C++ programs running on a 28-core shared-memory machine) than Privateer (11.5⇥), the prior automatic speculative-DOALL system with the highest applicability.

1 1

UPDATED LINK: Cliff Liu will present his Pre FPO "Sublinear Time Algorithms for Graph Problems" on Thursday, December 3, 2020 at 2pm via Zoom
by Nicki Mahler 03 Dec '20

03 Dec '20

Please use this updated link: [ https://princeton.zoom.us/j/8983320648?pwd=QWdPL3BuWGt2Y0s0RE9oUS9HYy8yZz09 | https://princeton.zoom.us/j/8983320648?pwd=QWdPL3BuWGt2Y0s0RE9oUS9HYy8yZz09 ] -------------- Cliff Liu will present his Pre FPO "Sublinear Time Algorithms for Graph Problems" on Thursday, December 3, 2020 at 2pm via Zoom. Zoom link: [ https://princeton.zoom.us/j/95875996152 | https://princeton.zoom.us/j/95875996152 ] The members of his committee are as follows: Examiners : Robert Tarjan (advisor), Matt Weinberg, Sepehr Assadi (Rutgers) Readers : Bernard Chazelle, Omri Weinstein (Columbia) Abstract: With the rapid growth of the internet, many optimization problems in recent big-data applications often exceed the capacity of traditional computing platforms. My goal is to lay the theoretical foundation of big-data analysis by designing algorithms on modern computing platforms to solve large-scale optimization problems under various resource constraints, with an emphasis on time efficiency and simplicity. The datasets in most applications are originated from or can be modeled as graphs, and this thesis focuses on solving graph problems. Usually, the graph is too large to store in a single memory, resulting in a very slow random access to the data. To capture this, one important computational model is streaming: we want to solve the problem using very limited space while minimizing the number of passes of scanning the entire data. Another framework to solve large-scale graph problems is to store the graph in a distributed manner and use the computational power of the distributed processors, which is called parallel computation. These two areas continue to be very active partly due to the success of the cloud computing platforms from Google, Microsoft, Amazon, and so on. We obtain faster and simpler algorithms in both streaming and parallel computation models for graph problems such as connectivity, bipartite matching, and maxflow. In particular, we solved three open problems. The first one is that given a graph of n vertices and m edges, does there exist a semi-streaming (using nearly n space) algorithm that computes the maximum weight bipartite matching in o(n) passes? We answer this question positively by giving an algorithm that runs in square root m passes. The algorithm relies on space-efficient versions of the interior point method, Laplacian system solving, and the generalized isolation lemma, all of which are not known before this work. The second problem is to break the square root n depth for computing maxflow in parallel. The square root n depth barrier exists for digraph reachability, matching, and other fundamental problems. Our solution is approximate, but only runs in n^{1/3} depth for unit-capacity graphs. The third problem is to give an o(log n) depth parallel algorithm for connectivity on a PRAM (parallel random access machine). All previous PRAM algorithms use at least log n depth. Our algorithm runs in O(log d + loglog n) depth where d is the diameter, which breaks the log n barrier for small-diameter graphs. Before our work, there is only an MPC (massively parallel computing, a model that is much stronger than PRAM) algorithm and it is very complicated. Our algorithm is simpler and more practical, albeit in a much weaker model. We also design several extremely simple algorithms for connectivity and bipartite matching. For the connectivity problem, we give several elegant algorithms (about five lines of code) in the MPC model, with a state-of-the-art running time of O(log n) for undirected graph. For the bipartite matching problem, we give a very simple streaming algorithm based on auctions that approximates the maximum matching to (1-eps) in O(eps^{-2}) passes and O(n) space, reducing the number of passes and space from previous work, which also has applications on faster MPC algorithms for matching.

1 0