|
3:00pm to 4:00pm - RH 306 - Special Colloquium Nick Cook - (UCLA) Large deviations for sparse random graphs Let $G=G(N,p)$ be an Erd\H{o}s--R\'enyi graph on $N$ vertices (where each pair is connected by an edge independently with probability $p$). We view $N$ as going to infinity, with $p$ possibly going to zero with $N$. What is the probability that $G$ contains twice as many triangles (triples of vertices with all three pairs connected) as we would expect? I will discuss recent progress on this ``infamous upper tail" problem, and more generally on tail estimates for counts of any fixed subgraph. These problems serve as a test bed for the emerging theory of \emph{nonlinear large deviations}, and also connect with issues in extending the theory of \emph{graph limits} to handle sparse graphs. In particular, I will discuss our approach to the upper tail problems via new versions of the classic regularity and counting lemmas from extremal combinatorics, specially tailored to the study of random graphs in the large deviations regime. This talk is based on joint work with Amir Dembo. |
|
4:00pm - RH 306 - Applied and Computational Mathematics Krithika Manohar - (Caltech) Optimal sensor placement using dimensionality reduction The scalable optimization of sensor and actuator placements remains an open challenge in estimation and control. In general, determining optimal sensor locations amounts to an intractable brute-force search among all candidate locations. My works exploits linear dimensionality reduction tools, including SVD and balanced model reduction, to bypass this combinatorial search. Sensor and actuator locations are computed using efficient matrix pivoting operations on the resulting low-dimensional representations, allowing runtime to scale only linearly with the number of candidate locations. Results are demonstrated on high-dimensional examples from imaging, fluids and control with thousands of candidate locations, and are comparable to placements computed using more expensive methods. If time permits, recent directions in nonlinear dimensionality reduction for forecasting will be discussed. |
|
11:00am to 12:00pm - RH 306 - Probability Steven Heilman - (USC) Minimal Gaussian partitions, clustering hardness and voting A single soap bubble has a spherical shape since it minimizes its surface area subject to a fixed enclosed volume of air. When two soap bubbles collide, they form a “double-bubble” composed of three spherical caps. The double-bubble minimizes total surface area among all sets enclosing two fixed volumes. This was proven mathematically in a landmark result by Hutchings-Morgan-Ritore-Ros and Reichardt using the calculus of variations in the early 2000s. The analogous case of three or more Euclidean sets is considered difficult if not impossible. However, if we replace Lebesgue measure in these problems with the Gaussian measure, then recent work of myself (for 3 sets) and of Milman-Neeman (for any number of sets) can actually solve these problems. We also use the calculus of variations. Time permitting, we will discuss an improvement to the Milman-Neeman result and applications to optimal clustering of data and to designing elections that are resilient to hacking. http://arxiv.org/abs/1901.03934 |
|
4:00pm to 5:00pm - RH 306 - Differential Geometry Xin Zhou - (UC, Santa Barbara) TBA |
|
12:00pm to 1:00pm - RH 340N - Probability Preprint Seminar John Peca-Medlin - (UCI) Universality of the cokernel of random integral matrices Viewed as a linear map on the integers, random integral matrices can be used to model many objects of interest outside probability, including class groups of number fields. Determining when a matrix is injective has been of interest for over half a century. Results by Komlos in the 1960s and later, followed then by more recent results by Tao and Vu and then Bourgain, Vu and P. M. Wood, established square Bernoulli matrices are injective with high probability. The next natural focus is to determine whether such a map is surjective. Recent results by M. M. Wood established the probability a square $n \times n$ matrix is surjective is asymptotically zero. So, what about the surjectivity of rectangular $n \times (n + u)$ matrices? Nguyen and Paquette show surjectivity holds almost surely when $u$ is sufficiently large for a large class of random integral models. So, what if $u$ is small? Nguyen and Wood then give the more general result that the cokernel of a rectangular matrix is isomorphic to a given finite abelian group, or is cyclic, using precise formulas with zeta functions, in agreement with distributions defined by Cohen and Lenstra. In particular, they show for $u = 1$, a rectangular matrix is surjective with positive probability $\prod_{k \ge 2} \zeta(k)^{-1} \approx 0.4358$. I will review the method and tools of Nguyen with Paquette and Wood, along with filling in some details from related questions. |
|
4:00pm to 5:00pm - RH 306 - Colloquium Andras Vasy - (Stanford University) Boundary rigidity and the local inverse problem for the geodesic X-ray transform on tensors In this talk, based on joint work with Plamen Stefanov and Gunther Uhlmann, I discuss the boundary rigidity problem on manifolds with boundary (for instance, a domain in Euclidean space with a perturbed metric), i.e. determining a Riemannian metric from the restriction of its distance function to the boundary. This corresponds to travel time tomography, i.e. finding the Riemannian metric from the time it takes for solutions of the corresponding wave equation to travel between boundary points. A version of this relates to finding the speed of seismic waves inside the Earth from travel time data, which in turn permits a study of the structure of the inside of the Earth. This non-linear problem in turn builds on the geodesic X-ray transform on such a Riemannian manifold with boundary. The geodesic X-ray transform on functions associates to a function its integral along geodesic curves, so for instance in domains in Euclidean space along straight lines. The X-ray transform on symmetric tensors is similar, but one integrates the tensor contracted with the tangent vector of the geodesics. I will explain how, under suitable convexity assumptions, one can invert the geodesic X-ray transform on functions, i.e. determine the function from its X-ray transform, in a stable manner, as well as the analogous tensor result, and the connection to the full boundary rigidity problem. |
|
4:00pm to 5:00pm - PSCB 140 - Graduate Seminar Paata Ivanisvili - (UC Irvine) What analysis and PDE have to do with combinatorics? Let X be a finite collection of sets. Given n>1 what is the maximal number of ways disjoint union of n sets (elements from X) is again a set in X? We will estimate this number in terms of n and the cardinality of X. |