Fast Point Transformer
2022-06-02 16:13 - 17:13 (America/New_York)
Abstract: The recent success of neural networks enables a better interpretation of 3D point clouds, but processing a large-scale 3D scene remains a challenging problem. Most current approaches divide a large-scale scene into small regions and combine the local predictions together. However, this scheme inevitably involves additional stages for pre- and post-processing and may also degrade the final output due to predictions in a local perspective. This talk introduces Fast Point Transformer that consists of a new lightweight self-attention layer. Our approach encodes continuous 3D coordinates, and the voxel hashing-based architecture boosts computational efficiency. The proposed method is demonstrated with 3D semantic segmentation and 3D detection. The accuracy of our approach is competitive to the best voxel-based method, and our network achieves 129 times faster inference time than the state-of-the-art, Point Transformer, with a reasonable accuracy trade-off in 3D semantic segmentation on S3DIS dataset.
Bio: Jaesik Park is an Assistant Professor at POSTECH. He received his Bachelor’s degree from Hanyang University in 2009, and he received his Master’s degree and Ph.D. degree from KAIST in 2011 and 2015, respectively. Before joining POSTECH, He worked at Intel as a research scientist, where he co-created the Open3D library. His research interests include image synthesis, scene understanding, and 3D reconstruction. He serves as a program committee at prestigious computer vision conferences, such as Area Chair for ICCV, CVPR, and ECCV.

Surface hopping algorithms for non-adiabatic quantum systems
2022-06-16 09:00 - 10:00 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
Interdisciplinary Science Seminar

Speaker: Jianfeng Lu, Duke UniversityTitle: Surface hopping algorithms for non-adiabatic quantum systems
Abstract: Surface hopping algorithm is widely used in chemistry for mixed quantum-classical dynamics. In this talk, we will discuss some of our recent works in mathematical understanding and algorithm development for surface hopping methods. These methods are based on stochastic approximations of semiclassical path-integral representation to the solution of multi-level Schrodinger equations; such methodology also extends to other high-dimensional transport systems.

Some new algorithms in statistical genomics
2022-06-23 09:00 - 10:00
Abstract: The statistical analysis of genomic data has incubated many innovations for computational method development. This talk will discuss some simple algorithms that may be useful in analyzing such data. Examples include algorithms for efficient resampling-based hypothesis testing, minimizing the sum of truncated convex functions, and fitting equality-constrained lasso problems. These algorithms have the potential to be used in other applications beyond statistical genomics.
Bio: Hui Jiang is an Associate Professor in the Department of Biostatistics at the University of Michigan. He received his Ph.D. in Computational and Mathematical Engineering from Stanford University. Before joining the University of Michigan, he was a postdoc in the Department of Statistics and Stanford Genome Technology Center at Stanford University. He is interested in developing statistical and computational methods for analyzing large-scale biological data generated using modern high-throughput technologies.

Entanglement and its key role in quantum information
2022-06-30 16:23 - 17:23
Abstract: Entanglement is a type of correlation found in composite quantum systems, connected with various non-classical phenomena. Currently, entanglement plays a key role in quantum information applications such as quantum computing, quantum communication, and quantum sensing. In this talk the concept of entanglement will be introduced along with various methods that have been proposed to detect and quantify it. The fundamental role of entanglement in both quantum theory and quantum technology will also be discussed.
Bio: Spyros Tserkis is a postdoctoral researcher at Harvard University, working on quantum information theory. Before joining Harvard in Fall 2021, he was a postdoctoral researcher at MIT and the Australian National University. He received his PhD from the University of Queensland.

The phenotype of the last universal common ancestor and the evolution of complexity
2022-07-07 09:00 - 10:00
Interdisciplinary Science Seminar

Speaker: Fouad El Baidouri, Broad Institute
Title: The phenotype of the last universal common ancestor and the evolution of complexity
Abstract: A fundamental concept in evolutionary theory is the last universal common ancestor (LUCA) from which all living organisms originated. While some authors have suggested a relatively complex LUCA it is still widely assumed that LUCA must have been a very simple cell and that life has subsequently increased in complexity through time. However, while current thought does tend towards a general increase in complexity through time in Eukaryotes, there is increasing evidence that bacteria and archaea have undergone considerable genome reduction during their evolution. This raises the surprising possibility that LUCA, as the ancestor of bacteria and archaea may have been a considerably complex cell. While hypotheses regarding the phenotype of LUCA do exist, all are founded on gene presence/absence. Yet, despite recent attempts to link genes and phenotypic traits in prokaryotes, it is still inherently difficult to predict phenotype based on the presence or absence of genes alone. In response to this, we used Bayesian phylogenetic comparative methods to predict ancestral traits. Testing for robustness to horizontal gene transfer (HGT) we inferred the phenotypic traits of LUCA using two robust published phylogenetic trees and a dataset of 3,128 bacterial and archaeal species.
Our results depict LUCA as a far more complex cell than has previously been proposed, challenging the evolutionary model of increased complexity through time in prokaryotes. Given current estimates for the emergence of LUCA we suggest that early life very rapidly evolved cellular complexity.

Topological and geometrical aspects of spinors in insulating crystals
2022-07-14 09:00 - 10:00
Abstract: Introducing internal degrees of freedom in the description of crystalline insulators has led to a myriad of theoretical and experimental advances. Of particular interest are the effects of periodic perturbations, either in time or space, as they considerably enrich the variety of electronic responses. Here, we present a semiclassical approach to transport and accumulation of general spinor degrees of freedom in adiabatically driven, weakly inhomogeneous crystals of dimensions one, two and three under external electromagnetic fields. Our approach shows that spatio-temporal modulations of the system induce a spinor current and density that is related to geometrical and topological objects — the spinor-Chern fluxes and numbers — defined over the higher-dimensional phase-space of the system, i.e., its combined momentum-position-time coordinates.
The results are available here: https://arxiv.org/abs/2203.14902
Bio: Ioannis Petrides is a postdoctoral fellow at the School of Engineering and Applied Sciences at Harvard University. He received his Ph.D. from the Institute for Theoretical Physics at ETH Zurich. His research focuses on the topological and geometrical aspects of condensed matter systems.

Infants’ sensory-motor cortices undergo microstructural tissue growth coupled with myelination
2022-07-21 09:00 - 10:00
Abstract: The establishment of neural circuitry during early infancy is critical for developing visual, auditory, and motor functions. However, how cortical tissue develops postnatally is largely unknown. By combining T1 relaxation time from quantitative MRI and mean diffusivity (MD) from diffusion MRI, we tracked cortical tissue development in infants across three timepoints (newborn, 3 months, and 6 months). Lower T1 and MD indicate higher microstructural tissue density and more developed cortex. Our data reveal three main findings: First, primary sensory-motor areas (V1: visual, A1: auditory, S1: somatosensory, M1: motor) have lower T1 and MD at birth than higher-level cortical areas. However, all primary areas show significant reductions in T1 and MD in the first six months of life, illustrating profound tissue growth after birth. Second, significant reductions in T1 and MD from newborns to 6-month-olds occur in all visual areas of the ventral and dorsal visual streams. Strikingly, this development was heterogenous across the visual hierarchies: Earlier areas are more developed with denser tissue at birth than higher-order areas, but higher-order areas had faster rates of development. Finally, analysis of transcriptomic gene data that compares gene expression in postnatal vs. prenatal tissue samples showed strong postnatal expression of genes associated with myelination, synaptic signaling, and dendritic processes. Our results indicate that these cellular processes may contribute to profound postnatal tissue growth in sensory cortices observed in our in-vivo measurements. We propose a novel principle of postnatal maturation of sensory systems: development of cortical tissue proceeds in a hierarchical manner, enabling the lower-level areas to develop first to provide scaffolding for higher-order areas, which begin to develop more rapidly following birth to perform complex computations for vision and audition.
This work is published here: https://www.nature.com/articles/s42003-021-02706-w

Statistical Mechanical theory for spatio-temporal evolution of Intra-tumor heterogeneity in cancers: Analysis of Multiregion sequencing data
2022-07-28 09:00 - 10:00 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
CMSA Interdisciplinary Science Seminar
Speaker: Sumit Sinha, Harvard University
Title: Statistical Mechanical theory for spatio-temporal evolution of Intra-tumor heterogeneity in cancers: Analysis of Multiregion sequencing data (https://arxiv.org/abs/2202.10595)
Abstract: Variations in characteristics from one region (sub-population) to another are commonly observed in complex systems, such as glasses and a collection of cells. Such variations are manifestations of heterogeneity, whose spatial and temporal behavior is hard to describe theoretically. In the context of cancer, intra-tumor heterogeneity (ITH), characterized by cells with genetic and phenotypic variability that co-exist within a single tumor, is often the cause of ineffective therapy and recurrence of cancer. Next-generation sequencing, obtained by sampling multiple regions of a single tumor (multi-region sequencing, M-Seq), has vividly demonstrated the pervasive nature of ITH, raising the need for a theory that accounts for evolution of tumor heterogeneity. Here, we develop a statistical mechanical theory to quantify ITH, using the Hamming distance, between genetic mutations in distinct regions within a single tumor. An analytic expression for ITH, expressed in terms of cell division probability (α) and mutation probability (p), is validated using cellular-automaton type simulations. Application of the theory successfully captures ITH extracted from M-seq data in patients with exogenous cancers (melanoma and lung). The theory, based on punctuated evolution at the early stages of the tumor followed by neutral evolution, is accurate provided the spatial variation in the tumor mutation burden is not large. We show that there are substantial variations in ITH in distinct regions of a single solid tumor, which supports the notion that distinct subclones could co-exist. The simulations show that there are substantial variations in the sub-populations, with the ITH increasing as the distance between the regions increases. The analytical and simulation framework developed here could be used in the quantitative analyses of the experimental (M-Seq) data. More broadly, our theory is likely to be useful in analyzing dynamic heterogeneity in complex systems such as supercooled liquids.
Bio: I am a postdoctoral fellow in Harvard SEAS (Applied Mathematics) and Dana Farber Cancer Institute (Data Science) beginning Feb 2022. I finished my PhD in Physics (Theoretical Biophysics) from UT Austin (Jan 2022) on “Theoretical and computational studies of growing tissue”. I pursued my undergraduate degree in Physics from the Indian Institute of Technology, Kanpur in India (2015). Boradly, I am interested in developing theoretical models, inspired from many-body statistical physics, for biological processes at different length and time scales.

Recent Advances on Maximum Flows and Minimum-Cost Flows
2022-08-10 09:00 - 10:00 | Virtual
Interdisciplinary Science Seminar

Speaker: Yang P. Liu

Title: Recent Advances on Maximum Flows and Minimum-Cost Flows

Abstract: We survey recent advances on computing flows in graphs, culminating in an almost linear time algorithm for solving minimum-cost flow and several other problems to high accuracy on directed graphs. Along the way, we will discuss intuitions from linear programming, graph theory, and data structures that influence these works, and the resulting natural open problems.
Bio: Yang P. Liu is a final-year graduate student at Stanford University. He is broadly interested in the efficient design of algorithms, particularly flows, convex optimization, and online algorithms. For his work, he has been awarded STOC and ITCS best student papers.

Exploring and Exploiting the Universality Phenomena in High-Dimensional Estimation and Learning
2022-08-11 09:00 - 10:00 | Hybrid
Interdisciplinary Science Seminar
Speaker: Yue M. Lu, Harvard University
Title: Exploring and Exploiting the Universality Phenomena in High-Dimensional Estimation and Learning
Abstract: Universality is a fascinating high-dimensional phenomenon. It points to the existence of universal laws that govern the macroscopic behavior of wide classes of large and complex systems, despite their differences in microscopic details. The notion of universality originated in statistical mechanics, especially in the study of phase transitions. Similar phenomena have been observed in probability theory, dynamical systems, random matrix theory, and number theory.
In this talk, I will present some recent progresses in rigorously understanding and exploiting the universality phenomena in the context of statistical estimation and learning on high-dimensional data. Examples include spectral methods for high-dimensional projection pursuit, statistical learning based on kernel and random feature models, and approximate message passing algorithms on highly structured, strongly correlated, and even (nearly) deterministic data matrices. Together, they demonstrate the robustness and wide applicability of the universality phenomena.
Bio: Yue M. Lu attended the University of Illinois at Urbana-Champaign, where he received the M.Sc. degree in mathematics and the Ph.D. degree in electrical engineering, both in 2007. He is currently Gordon McKay Professor of Electrical Engineering and of Applied Mathematics at Harvard University. He is also fortunate to have held visiting appointments at Duke University in 2016 and at the École Normale Supérieure (ENS) in 2019. His research interests include the mathematical foundations of statistical signal processing and machine learning in high dimensions.

Scalable Dynamic Graph Algorithms
2022-08-18 10:00 - 10:30 | CMSA Room G10, CMSA, 20 Garden Street, Cambridge, MA, 02138, United States
CMSA Interdisciplinary Science Seminar
Speaker: Quanquan Liu, Northwestern University
Title: Scalable Dynamic Graph Algorithms
Abstract: The field of dynamic graph algorithms seeks to understand and compute statistics on real-world networks that undergo changes with time. Some of these networks could have up to millions of edge insertions and deletions per second. In light of these highly dynamic networks, we propose various scalable and accurate graph algorithms for a variety of problems. In this talk, I will discuss new algorithms for various graph problems in the batch-dynamic model in shared-memory architectures where updates to the graph arrive in multiple batches of one or more updates. I’ll also briefly discuss my work in other dynamic models such as distributed dynamic models where the communication topology of the network also changes with time (ITCS 2022). In these models, I will present efficient algorithms for graph problems including k-core decomposition, low out-degree orientation, matching, triangle counting, and coloring.
Specifically, in the batch-dynamic model where we are given a batch of B updates, I’ll discuss an efficient O(B log^2 n) amortized work and O(log^2 n log log n) depth algorithm that gives a (2+epsilon)-approximation on the k-core decomposition after each batch of updates (SPAA 2022). We also obtain new batch-dynamic algorithms for matching, triangle counting, and coloring using techniques and data structures developed in our k-core decomposition algorithm. In addition to our theoretical results, we implemented and experimentally evaluated our k-core decomposition algorithm on a 30-core machine with two-way hyper-threading on 11 graphs of varying densities and sizes. Our experiments show improvements over state-of-the-art algorithms even on machines with only 4 cores (your standard laptop). I’ll conclude with a discussion of some open questions and potential future work that these lines of research inspire.
Bio: Quanquan C. Liu is a postdoctoral scholar at Northwestern University under the mentorship of Prof. Samir Khuller. She completed her PhD in Computer Science at MIT where she was advised by Prof. Erik Demaine and Prof. Julian Shun. Before that, she obtained her dual bachelor’s degree in computer science and math also at MIT. She has worked on a number of problems in algorithms and the intersection between theory and practice. Her most recent work focuses on scalable dynamic and static graph algorithms as well as differentially private graph algorithms for problems including k-core decomposition, densest subgraphs, subgraph counting, matching, maximal independent set and coloring. She has earned the Best Paper Award at SPAA 2022, a NSF Graduate Research Fellowship, and participated in the 2021 EECS Rising Stars workshop. Outside of research, she is extensively involved in programming outreach as a coach for the USA Computing Olympiad (USACO) and as a trainer for the North America Programming Camp (NAPC).
