Consider a uniformly random k-SAT instance with a fixed ratio of the number of clauses to the number of variables. As the clause-variable ratio increases, a curious phenomenon appears. With high probability the random instance is satisfiable below a certain threshold and unsatisfiable above the same threshold. This talk will give an overview of the problem of determining the precise threshold for random k-SAT, including various algorithmic approaches, the connections to statistical physics, Friedman's sharp threshold theorem, and the determination of the k-SAT threshold for large k by Ding, Sun, and Sly in 2014.

A subset $A\subseteq\mathbf{Z}$ of integers is free if for every two distinct subsets $B,B'\subseteq A$ we have $$\sum_{b\in B}b\neq\sum_{b'\in B'}b'.$$ Pisier asked if for every subset $A\subseteq\mathbf{Z}$ of integers the following two statement are equivalent:
(i) $A$ is a union of finitely many free sets.
(ii) There exists $\varepsilon>0$ such that every finite subset $B\subseteq A$ contains a free subset $C\subseteq B$ with $\vert C\vert\geq \varepsilon \vert B\vert$.
In a more general framework, the Pisier question can be seen as the problem of determining if statements (i) and (ii) are equivalent for subsets of a given structure with prescribed property. We study the problem for several structures including $B_h$-sets, arithmetic progressions, independent sets in hypergraphs and configurations in the Euclidean space.

This is joint work with Jaroslav Nešetřil, Christian Reiher and Vojtěch Rödl.

In this talk, we address the problem of continuous-time reinforcement learning in scenarios where the dynamics follow a stochastic differential equation. When the underlying dynamics remain unknown and we have access only to discrete-time information, how can we effectively conduct policy evaluation? We first demonstrate that the commonly used Bellman equation is a first-order approximation to the true value function. We then introduce higher order PDE-based Bellman equation called PhiBE. We show that the solution to the i-th order PhiBE is an i-th order approximation to the true value function. Additionally, even the first-order PhiBE outperforms the Bellman equation in approximating the true value function when the system dynamics change slowly. We develop a numerical algorithm based on Galerkin method to solve PhiBE when we possess only discrete-time trajectory data. Numerical experiments are provided to validate the theoretical guarantees we propose. 

I will introduce some recent progress towards understanding the scalability of Markov chain Monte Carlo (MCMC) methods and their comparative advantage with respect to variational inference. I will fact-check the folklore that "variational inference is fast but biased, MCMC is unbiased but slow". I will then discuss a combination of the two via reverse diffusion, which holds promise of solving some of the multi-modal problems. This talk will be motivated by the need for Bayesian computation in reinforcement learning problems as well as the differential privacy requirements that we face.

Can a purely combinatorial object be approximated by a continuum geometry? I will describe evidence that the answer is "yes''  if that object is a transitive directed acyclic graph, otherwise known as a discrete order, otherwise known as a causal set. In which case, the approximating continuum geometry must be pseudo-Riemannian with a "Lorentzian'' signature of $(-, +, +, \ldots, +)$. I will, along the way, explain the crucial difference between Riemannian and Lorentzian geometry: in the former case the geometry is local and in the latter the geometry is, if not actually nonlocal then teetering on the edge of being nonlocal.  If there is time I will describe a model of random orders called Transitive Percolation, which is the Lorentzian analogue of the Erdős-Renyi random graph and is an interesting toy model for a physical dynamics of discrete space-time.

We show that the growth of a unimodular random rooted tree (T,o) of degree bounded by d always exists, assuming its upper growth passes the critical threshold of the square root of d-1. This complements Timar's work who showed the possible nonexistence of growth below this threshold. The proof goes as follows. By Benjamini-Lyons-Schramm, we can realize (T,o) as the cluster of the root for some invariant percolation on the d-regular tree. Then we show that for such a percolation, the limiting exponent with which the lazy random walk returns to the cluster of its starting point always exists. We develop a new method to get this, that we call the 2-3-method, as the usual pointwise ergodic theorems do not seem to work here. We then define and prove the Cohen-Grigorchuk co-growth formula to the invariant percolation setting. This establishes and expresses the growth of the cluster from the limiting exponent, assuming we are above the critical threshold.

Interpretable machine learning has been widely deployed for scientific discoveries and decision-making, while its reliability hinges on the critical role of uncertainty quantification (UQ). In this talk, I will discuss UQ in two challenging scenarios motivated by scientific and societal applications: selective inference for large-scale graph learning and UQ for model-agnostic machine learning interpretations. Specifically, the first part concerns graphical model inference when only irregular, patchwise observations are available, a common setting in neuroscience, healthcare, genomics, and econometrics. To filter out low-confidence edges due to the irregular measurements, I will present a novel inference method that quantifies the uneven edgewise uncertainty levels over the graph as well as an FDR control procedure; this is achieved by carefully disentangling the dependencies across the graph and consequently yields more reliable graph selection. In the second part, I will discuss the computational and statistical challenges associated with UQ for feature importance of any machine learning model. I will take inspiration from recent advances in conformal inference and utilize an ensemble framework to address these challenges. This leads to an almost computationally free, assumption-light, and statistically powerful inference approach for occlusion-based feature importance. For both parts of the talk, I will highlight the potential applications of my research in science and society as well as how it contributes to more reliable and trustworthy data science.

Bio: Lili Zheng is a current postdoctoral researcher in the Department of Electrical and Computer Engineering at Rice University, mentored by Prof. Genevera I. Allen. Prior to this, she obtained her Ph.D. degree from the Department of Statistics at the University of Wisconsin-Madison, mentored by Prof. Garvesh Raskutti. Her research interests include graph learning, interpretable machine learning, uncertainty quantification, tensor data analysis, ensemble methods, and time series. Her website can be found at https://lili-zheng-stat.github.io

Tensor data, which exhibits more sophisticated structures than matrix data and brings unique statistical and computational challenges, has attracted a flurry of interest in modern statistics and data science. While tensor estimation has been extensively studied in recent literature, most existing methods rely heavily on idealistic assumptions (e.g., i.i.d. noise), which are often violated in real applications. In addition, uncertainty quantification for low-rank tensors, also known as statistical inference in this context, remains vastly underexplored.

In this talk, I will present our recent progress on tensor learning. The first part of the talk is concerned with heteroskedastic tensor clustering, which seeks to extract underlying cluster structures from tensor observations in the presence of heteroskedastic noise. A novel tensor clustering algorithm will be introduced to achieve exact clustering under an (almost) necessary signal-to-noise ratio condition for polynomial-time algorithms. The second part of the talk focuses on uncertainty quantification for tensor learning. Under a classical tensor PCA model, I will present a two-iteration alternating minimization procedure, and demonstrate that inference of principal components can be efficiently accomplished. These two developments represent the prolific interplay between statistics and computation in tensor learning.

Quantum computing made its name by solving a problem in number theory; namely, determining if factoring could be accomplished efficiently. Since then, there has been immense progress in development of quantum algorithms related to number theory. I'll give a perhaps idiosyncratic overview of the computational tools quantum computers bring to the table, with the goal of inspiring the audience to find new problems that quantum computers can solve.

[pre-talk at 1:20PM]

For the last 3.8 billion years, the large-scale structure of evolution has followed a pattern of speciation that can be described by branching trees. Recent work, especially on bacterial sequences, has established that despite their apparent complexity, these so-called phylogenetic or evolutionary trees exhibit two unexplained broad structural features which are consistent across evolutionary time. The first is that phylogenetic trees exhibit scale-invariant topology, which quantifies the fact that their branching lies in between the two extreme cases of balanced binary trees and maximally unbalanced ones. The second is that the backbones of phylogenetic trees exhibit bursts of diversification on all timescales. I present a coarse-grained statistical mechanics model of ecological niche construction coupled to a simple model of speciation, and use renormalization group arguments to show that the statistical scaling properties of the resultant phylogenetic trees recapitulate both the scale-invariant topology and the bursty pattern of diversification in time. These results show in principle how dynamical scaling laws of phylogenetic trees on long time-scales may emerge from generic aspects of the interplay between ecological and evolutionary processes, leading to scale interference.  

Finally, I will argue that these sorts of simplistic, minimal arguments might have a place in understanding other large-scale aspects of evolutionary biology. In particular I will mention two important biological questions, which, I will argue, require significant mathematical advances in order to answer them.  At present, we do not have even a qualitative understanding let alone a quantitative one: (1) the spontaneous emergence of the open-ended growth of complexity; (2) the response of evolving systems to perturbations and the implications for their control.  

Even though biology is intimidatingly complex, "everything has an exception", and there are a huge number of undetermined parameters, this work shows that mathematical reasoning may lead to useful new insights into the existence and universal characteristics of living systems.

Work performed in collaboration with Chi Xue and Zhiru Liu and supported by NASA through co-operative agreement NNA13AA91A through the NASA Astrobiology Institute for Universal Biology.
 

Emergent effects are commonly understood as novel properties, patterns, or behaviors of systems that are not present in their components, sometimes expressed as “the whole is more than the sum of its parts”.  I will discuss a framework that gives a measure of emergent effect as the “loss of exactness” computed from local structures, through category theory, homological algebra and quiver representations, and show that the derived functor that encodes emergent effects is related to information loss. I will also discuss potential connections to neural networks. I can also talk about other maths that could be used for quantifying emergence if you are not that into homological algebra. 

In this talk, we will present the development of Corona problem in sereval complex variables and discuss its relation to the solution of the sup-norm estimates for the Cauchy-Riemann equations. It includes the Berndtsson conjecture and its application to Corona problem. As well as the application of the  H\"ormander weighted $L^2$-estimates for $\overline{\partial}$  to the corona problem.

In this talk, I will discuss some recent developments and techniques in the study of the theory of holomorphic curves (Nevanlinna theory). In particular I will discuss the recent techniques of the so-called G.C.D. method as the applications of my recent work with Paul Vojta.