Georgia Institute of Technology College of Sciences

The rank r matrix completion problem studies whether a matrix where some of the entries have been filled in with generic complex numbers can be completed to a matrix of rank at most r. This problem is governed by the bipartite rigidity matroid, which is a matroid studied in combinatorial rigidity theory. We show that the study of the bipartite rigidity matroid is related to the study of tensor codes, a topic in information theory, and use this relation to understand new cases of both problems. Joint work with Joshua Brakensiek, Manik Dhar, Jiyang Gao, and Sivakanth Gopi.

There are many bizarre examples in the world of smooth 4-manifolds. We will describe some of these examples and discuss a tool from gauge theory that may be used to compute some of the invariants that distinguish these weird examples.

Finding Cheeger cuts of graphs is an NP-hard problem, and one often resorts to approximate solutions. In the literature, spectral graph theory provides the most popular approaches for obtaining such approximate solutions. Recently, K.C. Chang introduced a novel nonlinear spectral graph theory and proved that the seek of Cheeger cuts is equivalent to solving a constrained optimization problem. However, this resulting optimization problem is also very challenging as it involves a non-differentiable function over a non-convex set that is composed of simplex cells of different dimensions. In this talk, we will discuss an ADMM algorithm for solving this optimization problem and provide some convergence analysis. Experimental results will be presented for typical graphs, including Petersen's graph and Cockroach graphs, the well-known Zachary karate club graph, and some preliminary applications in material sciences.

We study nonlinear energy transfer and the existence of stationary measures in a class of degenerately forced SDEs on R^d with a quadratic, conservative nonlinearity B(x, x) constrained to possess various properties common to finite-dimensional fluid models and a linear damping term −Ax that acts only on a proper subset of phase space in the sense that dim(kerA) ≫ 1. Existence of a stationary measure is straightforward if kerA = {0}, but when the kernel of A is nontrivial a stationary measure can exist only if the nonlinearity transfers enough energy from the undamped modes to the damped modes. We develop a set of sufficient dynamical conditions on B that guarantees the existence of a stationary measure and prove that they hold “generically” within our constraint class of nonlinearities provided that dim(kerA) < 2d/3 and the stochastic forcing acts directly on at least two degrees of freedom. We also show that the restriction dim(kerA) < 2d/3 can be removed if one allows the nonlinearity to change by a small amount at discrete times. In particular, for a Markov chain obtained by evolving our SDE on approximately unit random time intervals and slightly perturbing the nonlinearity within our constraint class at each timestep, we prove that there exists a stationary measure whenever just a single mode is damped.

We say a class of graphs $\mathcal{F}$ is degree-bounded if there exists a function $f$ such that $\delta(G)\le f(\tau(G))$ for every $G\in\mathcal{F}$, where $\delta(G)$ denotes the minimum degree of $G$ and $\tau(G)$ is the biclique number of $G$, that is, the largest integer $t$ such that $G$ contains $K_{t,t}$ as a subgraph. Such a function $f$ is called a degree-bounding function for $\mathcal{F}$.

In joint work with Ant\'onio Gir\~ao, Zach Hunter, Rose McCarty and Alex Scott, we proved that every hereditary degree-bounded class $\mathcal{F}$ has a degree-bounding function that is singly exponential in the biclique number $\tau$. A more recent result by Ant\'onio Gir\~ao and Zach Hunter improved this bound to a polynomial function in $\tau$. In this talk, I will discuss examples and the recent results on degree-boundedness. 

In the 1990s, Arkadi Nemirovski asked the following question:

How hard is it to estimate a solution to unknown homogeneous linear difference equation with constant coefficients of order S, observed in the Gaussian noise on [0,N]?

The class of all such solutions, or "signals," is parametric---described by 2S complex parameters---but extremely rich: it includes the weighted sums of S exponentials, polynomials of degree S, harmonic oscillations with S arbitrary frequencies, and their algebraic combinations. Geometrically, this class is the union of all S-dimensional shift-invariant subspaces of the space of two-sided sequences, and of interest is the minimax risk on it with respect to the mean-squared error on [0,N]. I will present a recent result that shows this minimax risk to be O( S log(N) log(S)^2 ), improving over the state of the art by a polynomial in S factor, and coming within an O( log(S)^2 ) factor from the lower bound. It relies upon an approximation-theoretic construction related to minimal-norm interpolation over shift-invariant subspaces, in the spirit of the Landau-Kolmogorov problem, that I shall present in some detail. Namely, we will see that any shift-invariant subspace admits a bounded-support reproducing kernel whose spectrum has nearly the smallest possible Lp-energies for all p ≥ 1 at once.

The ($2$-dimensional) assignment problem is to find, in an edge weighted bipartite graph, an assignment (i.e., a perfect matching) of minimum total weight. Efficient algorithms for this problem have been known since the advent of modern algorithmic analysis. Moreover, if the edge weights are i.i.d. Exp(1) random variables and the host graph is complete bipartite, seminal results of Aldous state that the expected weight of the optimal assignment tends to $\zeta(2)$.

We consider high-dimensional versions of the random assignment problem. Here, we are given a cost array $M$, indexed by $[n]^k$, and with i.i.d. Exp(1) entries. The objective is to find a ${0,1}$-matrix A that minimizes $\sum_{x \in [n]^k} A_xM_x$, subject to the constraint that every axis-parallel line in A contains exactly one 1. This is the planar assignment problem, and when $k=2$ is equivalent to the usual random assignment problem. We prove that the expected cost of an optimal assignment is $\Theta(n^{k-2})$. Moreover, we describe a randomized algorithm that finds such an assignment with high probability. The main tool is iterative absorption, as developed by Glock, Kühn, Lo, and Osthus. The results answer questions of Frieze and Sorkin. The algorithmic result is in contrast to the axial assignment problem (in which A contains exactly one 1 in each axis-parallel co-dimension 1 hyperplane). For the latter, the best known bounds (which are due to Frankston, Kahn, Narayanan, and Park) exploit the connection between ``spread'' distributions and optimal assignments. Due to this reliance, no efficient algorithm is known.

Joint work with Ashwin Sah and Mehtaab Sawhney.