# Seminars & Events for PACM/Applied Mathematics Colloquium

##### Nonlinear echoes and Landau damping with insufficient regularity

In this talk, we will discuss recent advances towards understanding the regularity hypotheses in the theorem of Mouhot and Villani on Landau damping near equilibrium for the Vlasov-Poisson equations. We show that, in general, their theorem cannot be extended to any Sobolev space on the 1D torus. This is demonstrated by constructing arbitrarily small solutions with a sequence of nonlinear oscillations, known as plasma echoes, which damp at a rate arbitrarily slow compared to the linearized Vlasov equations. Some connections with hydrodynamic stability problems will be discussed if time permits.

##### Efficient Numerical Methods for Thermodynamic Averaging and Statistical Inference

Molecular models and data analytics problems give rise to gargantuan systems of stochastic differential equations (SDEs) whose paths ergodically sample multimodal probability distributions. An important challenge for the numerical analyst (or the chemist, or the physicist, or the engineer, or the data scientist) is the design of efficient numerical methods to generate these paths. For SDEs, the numerical perspective is just maturing, with important new methods (and, even more important, new procedures for their construction and analysis) becoming available.

##### Network clustering with higher order structures

Spectral clustering is a well-known way to partition a graph or network into clusters or communities with provable guarantees on the quality of the clusters. This guarantee is known as the Cheeger inequality and it holds for undirected graphs. We'll discuss a new generalization of the Cheeger inequality to higher-order structures in networks including network motifs. This is easy to implement and seamlessly generalizes spectral clustering to directed, signed, and many other types of complex networks. In particular, our generalization allow us to re-use the large history of existing ideas in spectral clustering including local methods, overlapping methods, and relationships with kernel k-means.

##### Optics and optimization

We will consider the following airplane boarding policy which was recently implemented by a few airlines: "Passengers with no overhead bin luggage board before those with such luggage". The reasoning for the policy was explained by the CEO of one of the companies as follows. Passengers with no overhead bin luggage tend to occupy the aisle for less time, therefore by boarding them first, the airline is able to push more people more quickly into the airplane, thus expediting the boarding process as a whole. In the talk we will show that what the airline wanted to do is to construct a thin focal lens in some space-time domain. Unfortunately, the shapes that correspond to the airline's policy are neither focal nor thin.

##### Testing Distribution Properties

Given samples from an unknown distribution p, is it possible to distinguish whether p belongs to some class of distributions C versus p being far from every distribution in C by some margin? This fundamental question has received extensive study in Statistics, Computer Science and several other fields. Still, even for basic classes of distributions such as unimodal, log-concave, or product the optimal sample complexity is unknown. We provide optimal testers for these and other families. In the process we strengthen the exchangeable pairs framework of [Chatterjee 2005]. (Based on works with Jayadev Acharya, Nishanth Dikkala, Gautam Kamath).

##### Counting Connected Graphs

Let C(n,k) be the number of labelled connected graphs with n vertices and n-1+k edges. For k=0 (trees) we have Cayley's Formula. We examine the asymptotics of C(n,k). There are several approaches involving supercritical dominant components in random graphs, local limit laws, Brownian excursions, Parking functions and other topics.

##### Statistics, Machine Learning, and Understanding the 2016 Election

Although 2016 is a highly unusual political year, elections and public opinion follow predictable statistical properties. I will review how the Presidential, Senate, and House races can be tracked and forecast from freely available polling data. Missing data can be filled in using a Google-Wide Association Study (GoogleWAS). Finally, simple statistics can be used to identify inequities such as partisan gerrymandering, and provide a tool for possible judicial relief. These examples show how statistics and machine learning can deepen an understanding of the U.S. political scene, even under extreme circumstances.

Samuel S.-H. Wang, Ph.D., Professor, Neuroscience Institute and Department of Molecular Biology, Princeton University

##### How Well Do Local Algorithms Solve Semidefinite Programs?

Several probabilistic models from high-dimensional statistics and machine learning reveal an intriguing -and yet poorly understood- dichotomy. Either simple local algorithms succeed in estimating the object of interest, or even sophisticated semi-definite programming (SDP) relaxations fail. In order to explore this phenomenon, we study a classical SDP relaxation of the minimum graph bisection problem, when applied to Erdos-Renyi random graphs with bounded average degree d>1, and obtain several types of results. First, we use a dual witness construction (using the so-called non-backtracking matrix of the graph) to upper bound the SDP value. Second, we prove that a simple local algorithm approximately solves the SDP to within a factor 2d^2/(2d^2+d−1) of the upper bound.

##### Kernel-based methods for Bandit Convex Optimization

Please click on the following link to access the abstract for this talk: http://www.pacm.princeton.edu/pacm-colloquium

##### Concurrent Disjoint Set Union

The disjoint set union problem is a classical problem in data structures with a simple and efficient sequential solution that has a notoriously complicated analysis. One application is to find strongly connected components in huge, implicitly defined graphs arising in model checking. In this application, the use of multiprocessors has the potential to produce significant speedups. We explore this possibility. We devise and analyze concurrent versions of standard sequential algorithms that use single and double compare-and-swap primitives for synchronization, making them wait-free. We obtain work bounds that grow logarithmically with the number of processors, suggesting the possibility of significant speedup in practice. This is ongoing joint work with Siddhartha Jayanti, an undergraduate at Princeton.

##### Turbulent weak solutions of the Euler equations

**This joint Math/PACM colloquium will be held at 4:00, Monday, December 5, in Fine 214.**

Motivated by Kolmogorov's theory of hydrodynamic turbulence, we consider dissipative weak solutions to the 3D incompressible Euler equations. We show that there exist infinitely many weak solutions of the 3D Euler equations, which are continuous in time, lie in a Sobolev space $H^s$ with respect to space, and they do not conserve the kinetic energy. Here the smoothness parameter $s$ is at the Onsager critical value $1/3$, consistent with Kolmogorov's $-4/5$ law for the third order structure functions. We shall also discuss bounds for the second order structure functions, which deviate from the classical Kolmogorov 1941 theory. This talk is based on joint work with T. Buckmaster and N. Masmoudi.

##### Quantum Oracle Classification: The Case of Group Structure

The Quantum Oracle Classification (QOC) problem is to classify a function, given only quantum black box access, into one of several classes without necessarily determining the entire function. Generally, QOC captures a very wide range of problems in quantum query complexity. However, relatively little is known about many of these problems. In this work, we analyze the a subclass of the QOC problems where there is a group structure. That is, suppose the range of the unknown function A is a commutative group G, which induces a commutative group law over the entire function space. Then we consider the case where A is drawn uniformly at random from some subgroup A of the function space. Moreover, there is a homomorpism f on A, and the goal is to determine f(A).

##### Survival and Schooling Hydrodynamics

The aqueous environment of natural swimmers mediates magnificent patterns of schooling as well as their escape and attack routines. We study the fluid mechanics of single and multiple swimmers through simulations that rely on state of the art multi-resolution vortex methods. Stochastic optimisation and machine learning algorithms are used to find optimal shapes and motions for single and synchronised patterns for multiple swimmers. I will discuss how the orchestration of body deformations and vortex dynamics can result in thrust and energy savings for these artificial swimmers and juxtapose these findings with swimming patterns of natural organisms. Lessons learned can assist the design and operation of energy efficient swimming devices.

##### Equiangular lines and spherical codes in Euclidean spaces

A family of lines through the origin in Euclidean space is called equiangular if any pair of lines defines the same angle. The problem of estimating the maximum cardinality of such a family in $\mathbb{R}^n$ was extensively studied for the last 70 years. Answering a question of Lemmens and Seidel from 1973, in this talk we show that for every fixed angle $\theta$ and sufficiently large $n$ there are at most $2n-2$ lines in $\mathbb{R}^n$ with common angle $\theta$. Moreover, this is achievable only when $\theta =\arccos\frac{1}{3}$. Various extensions of this result to the more general settings of lines with $k$ fixed angles and of spherical codes will be discussed as well. Joint work with I. Balla, F. Drexler and P. Keevash.

##### Sampling Nodes and Constructing Expanders Locally

In many real world applications we have only limited access to networks. For example when we crawl a social network or we design a peer-to-peer system we are restricted to access nodes only locally. In this talk we will analyze two classic problems in this setting. First we consider the problem of sampling nodes from a large graph according to a prescribed distribution by using only local random walks as the basic primitive. Our goal is to obtain algorithms that make a small number of queries to the graph but output a node that is sampled according to the prescribed distribution. Focusing on the uniform distribution case, we study the query complexity of three algorithms and show a near-tight bound expressed in terms of the parameters of the graph such as average degree and the mixing time.

##### How Far Are We From Having a Satisfactory Theory of Clustering?

Unsupervised learning is widely recognized as one of the most important challenges facing machine learning nowadays. However, unlike supervised learning, our current theoretical understanding of those tasks, and in particular of clustering, is very rudimentary. Although hundreds of clustering papers are being published every year, there is hardly any work reasoning about clustering independently of any particular algorithm, objective function, or generative data model. My talk will focus on such clustering research. I will discuss two aspects in which theory could play a significant role in guiding the use of clustering tools. The first is model selection - how should a user pick an appropriate clustering tool for a given clustering problem, and how should the parameters of such an algorithmic tool be tuned?

##### Recent progress in object recognition and symmetry detection in digital images

I will survey developments in the application of invariants of various types, including differential invariant signatures and joint invariant histograms, for object recognition and symmetry detection in digital images. Recent applications, including automated jigsaw puzzle assembly and cancer detection, will be presented.

##### Stochastic Models in Robotics and Structural Biology

Many stochastic problems of interest in engineering and science involve random rigid-body motions. In this talk, a variety of stochastic phenomena that evolve on the group of rigid-body motions will be discussed together with tools from harmonic analysis and Lie theory to solve the associated equations. These include mobile robot path planning, statistical mechanics of DNA, and problems in image processing. Current work on multi-robot team diagnosis and repair, information fusion, and self-replicating robots will also be discussed. In order to quantify the robustness of such robots, measures of the degree of environmental uncertainty that they can handle need to be computed.

##### Sample-optimal inference, computational thresholds, and the methods of moments

We propose an efficient meta-algorithm for Bayesian inference problems based on low-degree polynomials, semidefinite programming, and tensor decomposition. The algorithm is inspired by recent lower bound constructions for sum-of-squares and related to the method of moments. Our focus is on sample complexity bounds that are as tight as possible (up to additive lower-order terms) and often achieve statistical thresholds or conjectured computational thresholds. Our algorithm recovers the best known bounds for partial recovery in the stochastic block model, a widely-studied class of inference problems for community detection in graphs.

##### Physics in the complex plane

The average quantum physicist on the street would say that a quantum-mechanical Hamiltonian must be Dirac Hermitian (invariant under combined matrix transposition and complex conjugation) in order to guarantee that the energy eigenvalues are real and that time evolution is unitary. However, the Hamiltonian $H=p^2+ix^3$, which is obviously not Dirac Hermitian, has a positive real discrete spectrum and generates unitary time evolution, and thus it defines a fully consistent and physical quantum theory. Evidently, the axiom of Dirac Hermiticity is too restrictive. While $H=p^2+ix^3$ is not Dirac Hermitian, it is PT symmetric; that is, invariant under combined parity P (space reflection) and time reversal T. The quantum mechanics defined by a PT-symmetric Hamiltonian is a complex generalization of ordinary quantum mechanics.