Georgia Institute of Technology College of Sciences

Given a simple graph on $n$ vertices and a parameter $k$, the triangle-densest-$k$-subgraph problem is known to be computationally hard in the worst case. To circumvent the computational hardness, we study an average-case model where a triangle-dense subgraph on $k$ vertices is planted in an Erd\H{o}s--R\'enyi random graph on $n$ vertices. For the recovery of the planted subgraph, we propose a simple spectral algorithm and a semidefinite program, both of which use a graph matrix whose entries are local signed triangle counts. Theoretical guarantees for these algorithms are established through spectral analysis of the graph matrix. Finally, we provide evidence showing a statistical-to-computational gap analogous to that for the planted clique problem. The computational threshold in terms of the subgraph size $k$ is at least $\sqrt{n}$ in the framework of low-degree polynomial algorithms, while the information-theoretic threshold is at most logarithmic in $n$. Joint work with Cheng Mao and Benjamin McKenna.

Spin glasses are disordered statistical physics system with both ferromagnetic and anti-ferromagnetic spin interactions. The Gibbs measure belongs to the exponential family with parameters, such as inverse temperature $\beta>0$ and external field $h\in R$.  A fundamental statistical problem is to estimate the system parameters from a single sample of the ground truth. In 2007, Chatterjee first proved that under reasonable conditions, for spin glass models with $h=0$, the maximum pseudo-likelihood estimator for $\beta$ is $\sqrt{N}$-consistent. This is in contrast to the existing estimation results for classical non-disordered models. However, Chatterjee's approach has been restricted to the single parameter estimation setting.  The joint parameter estimation of $(\beta,h)$ for spin glasses has remained open since then. In this talk, I will introduce a new idea to show that under some easily verifiable conditions,  the bi-variate maximum pseudo-likelihood estimator is jointly $\sqrt{N}$-consistent for a large collection of spin glasses, including the Sherrington-Kirkpatrick model and its diluted variants. Based on joint work with Wei-Kuo Chen, Arnab Sen. 

Chambert-Loir and Ducros have introduced a theory of real-valued smooth differential forms on Berkovich spaces that play the role of smooth forms on complex varieties.  We compute the associated Dolbeault cohomology groups of curves by reducing to the case of metric graphs.  I'll introduce smooth forms on graphs, and explain how the theory in CLD has to be modified in order to get finite-dimensional cohomology groups.

We discuss the recent progress on Graham's Conjecture which states that for any subset $S \subseteq \mathbb{Z}_p \setminus \{0\}$, there exists an ordering of the elements $s_1, \cdots, s_m$ of $S$ such that the partial sums $\sum_{i = 1}^k s_i$ are all distinct. This was very recently proven for all sufficiently large primes by Pham and Sauermann, however our work focuses on the more general setting where $\mathbb{Z}_p$ is replaced by an arbitrary finite group, where the result is also conjectured to hold.

By considering the Cayley Graph, we can translate the problem into the purely graph theoretic problem of finding a rainbow path of length $d - 1$ in any $d$-regular properly edge-colored directed graph. We give an asymptotic result which builds on work by Bucić, Frederickson, Müyesser, Pokrovskiy, and Yepremyan, and shows that we can find a path of length $(1 - o(1)) d$. This corresponds to showing that for any subset $S \subseteq G$, there exists a dense subset $S' \subseteq G$ and an ordering $s'_1, \cdots, s'_m$ of the elements of $S'$ such that the partial products $\prod_{i  = 1}^k s'_i$ are all distinct.