Georgia Institute of Technology College of Sciences

In this talk we introduce some machine learning problems in the setting of undirected graphical models, also known as spin systems. We take proper colorings as a representative example of a hard-constraint graphical model. The classic problem of sampling a proper coloring uniformly at random of a given graph has been well-studied. Here we consider two inverse problems: Given random colorings of an unknown graph G, can we recover the underlying graph G exactly? If we are also given a candidate graph H, can we tell if G=H? The former problem is known as structure learning in the machine learning field and the latter is called identity testing. We show the complexity of these problems in different range of parameters and compare these results with the corresponding decision and sampling problems. Finally, we give some results of the analogous problems for the Ising model, a typical soft-constraint model. Based on joint work with Ivona Bezakova, Antonio Blanca, Daniel Stefankovic and Eric Vigoda.

In first-passage percolation, we place i.i.d. nonnegative weights (t_e) on the edges of a graph and consider the induced weighted graph metric T(x,y). When the underlying graph is the two-dimensional square lattice, there is a phase transition in the model depending on the probability p that an edge weight equals zero: for p<1/2, the metric T(0,x) grows linearly in x, whereas for p>1/2, it remains stochastically bounded. The critical case occurs for p=1/2, where there are large but finite clusters of zero-weight edges. In this talk, I will review work with Wai-Kit Lam and Xuan Wang in which we determine the rate of growth for T(0,x) up to a constant factor for all critical distributions. Then I will explain recent work with Jack Hanson and Wai-Kit Lam in which we determine the "time constant" (leading order constant in the rate of growth) in the special case where the graph is the triangular lattice, and the weights are placed on the vertices. This is the only class of distributions known where this time constant is computable: we find that it is an explicit function of the infimum of the support of t_e intersected with (0,\infty).

We will consider the problem of estimating the singularity probability of sparse Bernoulli matrices, and a related question of anti-concentration of weighted sums of dependent Bernoulli(p) variables.

Based on joint work with Alexander Litvak.

In asymptotic analysis and numerical approximation of highly-oscillatory evolution problems, it is commonly supposed that the oscillation frequency is either constant or, at least, bounded from below by a strictly positive constant uniformly in time. Allowing for the possibility that the frequency actually depends on time and vanishes at some instants introduces additional difficulties from both the asymptotic analysis and numerical simulation points of view. I will present a first step towards the resolution of these difficulties. In particular, we show that it is still possible in this situation to infer the asymptotic behavior of the solution at the price of more intricate computations and we derive a second order uniformly accurate numerical method.