1/27/2022 – Interdisciplinary Science Seminar
2022-01-27 14:54 - 16:54 (America/New_York)
Title: Polynomials vanishing at lattice points in convex sets
Abstract: Let P be a convex subset of R^2. For large d, what is the smallest degree r_d of a polynomial vanishing at all lattice points in the dilate d*P? We show that r_d / d converges to some positive number, which we compute for many (but maybe not all) triangles P.

2/3/2022 – Interdisciplinary Science Seminar
2022-02-03 14:57 - 16:57
Title:Quasiperiodic prints from triply periodic blocks
Abstract: Slice a triply periodic wooden sculpture along an irrational plane. If you ink the cut surface and press it against a page, the pattern you print will be quasiperiodic. Patterns like these help physicists see how metals conduct electricity in strong magnetic fields. I’ll show you some block prints that imitate the printing process described above, and I’ll point out the visual features that reveal conductivity properties.
Interactive slides:https://www.ihes.fr/~fenyes/seeing/slices/

2/10/2022 – Interdisciplinary Science Seminar
2022-02-10 15:00 - 16:00
Title: Metric Algebraic Geometry
Abstract: A real algebraic variety is the set of points in real Euclidean space that satisfy a system of polynomial equations. Metric algebraic geometry is the study of properties of real algebraic varieties that depend on a distance metric. In this talk, we introduce metric algebraic geometry through a discussion of Voronoi cells, bottlenecks, and the reach of an algebraic variety. We also show applications to the computational study of the geometry of data with nonlinear models.

Sparse Markov Models for High-dimensional Inference
2022-02-17 15:05 - 16:05
Abstract: Finite order Markov models are theoretically well-studied models for dependent data. Despite their generality, application in empirical work when the order is larger than one is quite rare. Practitioners avoid using higher order Markov models because (1) the number of parameters grow exponentially with the order, (2) the interpretation is often difficult. Mixture of transition distribution models (MTD) were introduced to overcome both limitations. MTD represent higher order Markov models as a convex mixture of single step Markov chains, reducing the number of parameters and increasing the interpretability. Nevertheless, in practice, estimation of MTD models with large orders are still limited because of curse of dimensionality and high algorithm complexity. Here, we prove that if only few lags are relevant we can consistently and efficiently recover the lags and estimate the transition probabilities of high order MTD models. Furthermore, we show that using the selected lags we can construct non-asymptotic confidence intervals for the transition probabilities of the model. The key innovation is a recursive procedure for the selection of the relevant lags of the model. Our results are based on (1) a new structural result of the MTD and (2) an improved martingale concentration inequality. Our theoretical results are illustrated through simulations.

Singular Set in Obstacle Problems
2022-02-24 15:08 - 16:08
Abstract: In this talk we describe a new method to study the singular set in the obstacle problem. This method does not depend on monotonicity formulae and works for fully nonlinear elliptic operators. The result we get matches the best-known result for the case of Laplacian.

Towards Understanding Training Dynamics for Mildly Overparametrized Models
2022-03-03 15:11 - 16:11
Abstract: While over-parameterization is widely believed to be crucial for the success of optimization for the neural networks, most existing theories on over-parameterization do not fully explain the reason — they either work in the Neural Tangent Kernel regime where neurons don’t move much, or require an enormous number of neurons. In this talk I will describe our recent works towards understanding training dynamics that go beyond kernel regimes with only polynomially many neurons (mildly overparametrized). In particular, we first give a local convergence result for mildly overparametrized two-layer networks. We then analyze the global training dynamics for a related overparametrized tensor model. For both works, we rely on a key intuition that neurons in overparametrized models work in groups and it’s important to understand the behavior of an average neuron in the group. Based on two works: https://arxiv.org/abs/2102.02410 and https://arxiv.org/abs/2106.06573.
Bio: Professor Rong Ge is Associate Professor of Computer Science at Duke University. He received his Ph.D. from the Computer Science Department of Princeton University, supervised by Sanjeev Arora. He was a post-doc at Microsoft Research, New England. In 2019, he received both a Faculty Early Career Development Award from the National Science Foundation and the prestigious Sloan Research Fellowship. His research interest focus on theoretical computer science and machine learning. Modern machine learning algorithms such as deep learning try to automatically learn useful hidden representations of the data. He is interested in formalizing hidden structures in the data and designing efficient algorithms to find them. His research aims to answer these questions by studying problems that arise in analyzing text, images, and other forms of data, using techniques such as non-convex optimization and tensor decompositions.

Virtual Teams in Gig Economy — An End-to-End Data Science Approach
2022-03-10 15:13 - 16:13
Abstract: The gig economy provides workers with the benefits of autonomy and flexibility, but it does so at the expense of work identity and co-worker bonds. Among the many reasons why gig workers leave their platforms, an unexplored aspect is the organization identity. In a series of studies, we develop a team formation and inter-team contest at a ride-sharing platform. We employ an end-to-end data science approach, combining methodologies from randomized field experiments, recommender systems, and counterfactual machine learning. Together, our results show that platform designers can leverage team identity and team contests to increase revenue and worker engagement in a gig economy.
Bio: Wei Ai is an Assistant Professor in the College of Information Studies (iSchool) and the Institute for Advanced Computer Studies (UMIACS) at the University of Maryland. His research interest lies in data science for social good, where the advances of machine learning and data analysis algorithms translate into measurable impacts on society. He combines machine learning, causal inference, and field experiments in his research, and has rich experience in collaborating with industrial partners. He earned his Ph.D. from the School of Information at the University of Michigan. His research has been published in top journals and conferences, including PNAS, ACM TOIS, WWW, and ICWSM.

On optimization and generalization in deep learning
2022-03-17 15:15 - 16:15
Abstract: Deep neural networks have achieved significant empirical success in many fields, including the fields of computer vision and natural language processing. Along with its empirical success, deep learning has been theoretically shown to be attractive in terms of its expressive power. However, the theory of expressive power does not ensure that we can efficiently find an optimal solution in terms of optimization and generalization, during the optimization process. In this talk, I will discuss some mathematical properties of optimization and generalization for deep neural networks.

An operadic structure on supermoduli spaces
2022-03-24 15:17 - 17:17
Abstract: The operadic structure on the moduli spaces of algebraic curves encodes in a combinatorial way how nodal curves in the boundary can be obtained by glueing smooth curves along marked points. In this talk, I will present a generalization of the operadic structure to moduli spaces of SUSY curves (or super Riemann surfaces). This requires colored graphs and generalized operads in the sense of Borisov-Manin. Based joint work with Yu. I. Manin and Y. Wu. https://arxiv.org/abs/2202.10321

Compactification of an embedded vector space and its combinatorics
2022-03-31 15:20 - 17:20
Abstract: Matroids are combinatorial abstractions of vector spaces embedded in a coordinate space. Many fundamental questions have been open for these classical objects. We highlight some recent progress that arise from the interaction between matroid theory and algebraic geometry. Key objects involve compactifications of embedded vector spaces, and an exceptional Hirzebruch-Riemann-Roch isomorphism between the K-ring of vector bundles and the cohomology ring of stellahedral varieties.

The space of vector bundles on spheres: algebra, geometry, topology
2022-04-07 15:22 - 17:22
Abstract: Bott periodicity relates vector bundles on a topological space X to vector bundles on X “times a sphere”. I’m not a topologist, so I will try to explain an algebraic or geometric incarnation, in terms of vector bundles on the Riemann sphere. I will attempt to make the talk introductory, and (for the most part) accessible to those in all fields, at the expense of speaking informally and not getting far. This relates to recent work of Hannah Larson, as well as joint work with (separately) Larson and Jim Bryan.

SIMPLEs: a single-cell RNA sequencing imputation strategy preserving gene modules and cell clusters variation
2022-04-14 09:00 - 10:00
Abstract: A main challenge in analyzing single-cell RNA sequencing (scRNA-seq) data is to reduce technical variations yet retain cell heterogeneity. Due to low mRNAs content per cell and molecule losses during the experiment (called ‘dropout’), the gene expression matrix has a substantial amount of zero read counts. Existing imputation methods treat either each cell or each gene as independently and identically distributed, which oversimplifies the gene correlation and cell type structure. We propose a statistical model-based approach, called SIMPLEs (SIngle-cell RNA-seq iMPutation and celL clustErings), which iteratively identifies correlated gene modules and cell clusters and imputes dropouts customized for individual gene module and cell type. Simultaneously, it quantifies the uncertainty of imputation and cell clustering via multiple imputations. In simulations, SIMPLEs performed significantly better than prevailing scRNA-seq imputation methods according to various metrics. By applying SIMPLEs to several real datasets, we discovered gene modules that can further classify subtypes of cells. Our imputations successfully recovered the expression trends of marker genes in stem cell differentiation and can discover putative pathways regulating biological processes.

Secure Multi-Party Computation: from Theory to Practice
2022-04-21 09:00 - 10:00
Abstract:
Encryption is the backbone of cybersecurity. While encryption can secure data both in transit and at rest, in the new era of ubiquitous computing, modern cryptography also aims to protect data during computation. Secure multi-party computation (MPC) is a powerful technology to tackle this problem, which enables distrustful parties to jointly perform computation over their private data without revealing their data to each other. Although it is theoretically feasible and provably secure, the adoption of MPC in real industry is still very much limited as of today, the biggest obstacle of which boils down to its efficiency.
My research goal is to bridge the gap between the theoretical feasibility and practical efficiency of MPC. Towards this goal, my research spans both theoretical and applied cryptography. In theory, I develop new techniques for achieving general MPC with the optimal complexity, bringing theory closer to practice. In practice, I design tailored MPC to achieve the best concrete efficiency for specific real-world applications. In this talk, I will discuss the challenges in both directions and how to overcome these challenges using cryptographic approaches. I will also show strong connections between theory and practice.
Biography:
Peihan Miao is an assistant professor of computer science at the University of Illinois Chicago (UIC). Before coming to UIC, she received her Ph.D. from the University of California, Berkeley in 2019 and had brief stints at Google, Facebook, Microsoft Research, and Visa Research. Her research interests lie broadly in cryptography, theory, and security, with a focus on secure multi-party computation — especially in incorporating her industry experiences into academic research.

Intersection number and systole on hyperbolic surfaces
2022-04-28 15:33 - 17:33
Abstract: Let X be a compact hyperbolic surface. We can see that there is a constant C(X) such that the intersection number of the closed geodesics is leq C(X) times the product of their lengths. Consider the optimum constant C(X). In this talk, we describe its asymptotic behavior in terms of systole, length of the shortest closed geodesic on X.

Qianfang: a type-safe and data-driven healthcare system starting from Traditional Chinese Medicine
2022-05-05 15:36 - 17:36
Abstract: Although everyone talks about AI + healthcare, many people were unaware of the fact that there are two possible outcomes of the collaboration, due to the inherent dissimilarity between the two giant subjects. The first possibility is healthcare-leads, and AI is for building new tools to make steps in healthcare easier, better, more effective or more accurate. The other possibility is AI-leads, and therefore the protocols of healthcare can be redesigned or redefined to make sure that the whole infrastructure and pipelines are ideal for running AI algorithms.
Our system Qianfang belongs to the second category. We have designed a new kind of clinic for the doctors and patients, so that it will be able to collect high quality data for AI algorithms. Interestingly, the clinic is based on Traditional Chinese Medicine (TCM) instead of modern medicine, because we believe that TCM is more suitable for AI algorithms as the starting point.
In this talk, I will elaborate on how we convert TCM knowledge into a modern type-safe large-scale system, the mini-language that we have designed for the doctors and patients, the interpretability of AI decisions, and our feedback loop for collecting data.
Our project is still on-going, not finished yet.Bio: Yang Yuan is now an assistant professor at IIIS, Tsinghua. He finished his undergraduate study at Peking University in 2012. Afterwards, he received his PhD at Cornell University in 2018, advised by Professor Robert Kleinberg. During his PhD, he was a visiting student at MIT/Microsoft New England (2014-2015) and Princeton University (2016 Fall). Before joining Tsinghua, he spent one year at MIT Institute for Foundations of Data Science (MIFODS) as a postdoc researcher. He now works on AI+Healthcare, AI Interpretability and AI system.

Geometric Models for Sets of Probability Measures
2022-05-12 15:38 - 17:38
Abstract: Many statistical and computational tasks boil down to comparing probability measures expressed as density functions, clouds of data points, or generative models. In this setting, we often are unable to match individual data points but rather need to deduce relationships between entire weighted and unweighted point sets. In this talk, I will summarize our team’s recent efforts to apply geometric techniques to problems in this space, using tools from optimal transport and spectral geometry. Motivated by applications in dataset comparison, time series analysis, and robust learning, our work reveals how to apply geometric reasoning to data expressed as probability measures without sacrificing computational efficiency.

The geometry of conditional independence models with hidden variables
2022-05-19 09:00 - 10:00
Abstract: Conditional independence (CI) is an important tool instatistical modeling, as, for example, it gives a statistical interpretation to graphical models. In general, given a list of dependencies among random variables, it is difficult to say which constraints are implied by them. Moreover, it is important to know what constraints on the random variables are caused by hidden variables. On the other hand, such constraints are corresponding to some determinantal conditions on the tensor of joint probabilities of the observed random variables. Hence, the inference question in statistics relates to understanding the algebraic and geometric properties of determinantal varieties such as their irreducible decompositions or determining their defining equations. I will explain some recent progress that arises by uncovering the link to point configurations in matroid theory and incidence geometry. This connection, in particular, leads to effective computational approaches for (1) giving a decomposition for each CI variety; (2) identifying each component in the decomposition as a matroid variety; (3) determining whether the variety has a real point or equivalently there is a statistical model satisfying a given collection of dependencies. The talk is based on joint works with Oliver Clarke, Kevin Grace, and Harshit Motwani.
The papers are available on arxiv: https://arxiv.org/pdf/2011.02450
and https://arxiv.org/pdf/2103.16550.pdf

Extinction and coexistence for reaction-diffusion systems on metric graphs
2022-05-26 09:00 - 10:00
Abstract: In spatial population genetics, it is important to understand the probability of extinction in multi-species interactions such as growing bacterial colonies, cancer tumor evolution and human migration. This is because extinction probabilities are instrumental in determining the probability of coexistence and the genealogies of populations. A key challenge is the complication due to spatial effect and different sources of stochasticity. In this talk, I will discuss about methods to compute the probability of extinction and other long-time behaviors for stochastic reaction-diffusion equations on metric graphs that flexibly parametrizes the underlying space. Based on recent joint work with Adrian Gonzalez-Casanova and Yifan (Johnny) Yang.

Fast Point Transformer
2022-06-02 16:13 - 17:13
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).
