Georgia Institute of Technology College of Sciences

In this dissertation we study a variety of graph-theoretic problems lying at the intersection of mathematics, computer science, and statistics. This work consists of three parts, all of which use probabilistic techniques. 

In Part 1, we consider structurally constrained graphs and hypergraphs. We examine a celebrated conjecture of Alon, Krivelevich, and Sudakov regarding vertex coloring. Our results provide improved bounds in all known cases for which the conjecture holds. We introduce a generalized notion of local sparsity and study the independence and chromatic numbers of graphs satisfying this property. We also consider multipartite hypergraphs, a natural extension of bipartite graphs. We show how certain probabilistic techniques for problems on bipartite graphs can be adapted to multipartite hypergraphs, and are therefore able to extend and generalize a number of results.

In Part 2, we investigate edge coloring from an algorithmic standpoint. We focus on multigraphs of bounded maximum degree, i.e., $\Delta(G) = O(1)$. Following the so-called augmenting subgraph approach, we design deterministic and randomized algorithms using a near-optimal number of colors in the sequential setting as well as in the LOCAL model of distributed computing. Additionally, we study list-edge-coloring for list assignments satisfying certain local constraints, and describe a polynomial-time algorithm to compute such a coloring.

Finally, in Part 3, we explore a number of statistical inference problems in random hypergraph models. Specifically, we consider the statistical-computational gap for finding large independent sets in sparse random hypergraphs, and the computational threshold for the detection of planted dense subhypergraphs (a generalization of the classical planted clique problem). We explore the power and limitations of low-degree polynomial algorithms, a powerful class of algorithms which includes the class of local algorithms as well as approximate message passing and power iteration.

Speaker will present in person.

Hermitian matrices have real eigenvalues and an orthonormal set of eigenvectors. Do smooth Hermitian matrix valued functions have smooth eigenvalues and eigenvectors? Starting from such question, we will first review known results on the smooth eigenvalue and singular values decompositions of matrices that depend on one or several parameters, and then focus on our contribution, which has been that of devising topological tools to detect and approximate parameters' values where eigenvalues or singular values of a matrix valued function are degenerate (i.e. repeated or zero).

The talk will be based on joint work with Luca Dieci (Georgia Tech) and Alessandra Papini (Univ. of Florence).

A fundamental conjecture in number theory is the Riemann hypothesis, which implies the prime number theorem with an optimally strong error term. While a proof remains elusive, many results in number theory can nonetheless be proved using weaker inputs. I will discuss how one such weaker input, subconvexity, can be used to prove strong results on the equidistribution of geometric objects such as lattice points on the sphere. If time permits, I will also discuss how various proofs of subconvexity reduce to understanding period integrals of automorphic forms.

In this talk, we discuss generative modeling algorithms motivated by the time reversal and reflection properties of diffusion processes. Score-based diffusion models (SBDM) have recently emerged as state-of-the-art approaches for image generation. We develop SBDMs in the infinite-dimensional setting, that is, we model the training data as functions supported on a rectangular domain. Besides the quest for generating images at ever higher resolution, our primary motivation is to create a well-posed infinite-dimensional learning problem so that we can discretize it consistently at multiple resolution levels. We demonstrate how to overcome two shortcomings of current SBDM approaches in the infinite-dimensional setting by ensuring the well-posedness of forward and reverse processes, and derive the convergence of the approximation of multilevel training. We illustrate that approximating the score function with an operator network is beneficial for multilevel training.

In the second part of this talk, we propose the Reflected Schrodinger Bridge algorithm: an entropy-regularized optimal transport approach tailored for generating data within diverse bounded domains. We derive reflected forward-backward stochastic differential equations with Neumann and Robin boundary conditions, extend divergence-based likelihood training to bounded domains, and demonstrate its scalability in constrained generative modeling.