CCSI/GMOS Student Seminar

Speaker 1: Sophie Yu
Title: Detection and Recovery thresholds for Graph Matching

Abstract: This talk focuses on detection and recovery problems of matching two Erdos-Renyi random graphs. Specifically, for detection, we aim to decide whether the two observed graphs are independent, or edge-correlated under some latent node correspondence. For recovery, our goal is to recover the latent node correspondence given the two graphs are edge-correlated. In the dense graph regime, we prove that both detection and recovery exhibit an "all-or-nothing" phase transition at a sharp threshold. For sparse graphs, we identify the information-theoretic threshold within some constant factor. 

This talk is based on the joint work with Jiaming Xu and Yihong Wu.
https://arxiv.org/abs/2008.10097
https://arxiv.org/abs/2102.00082

Speaker 2: Elizabeth Yang
Title: Domain Sparsification of Discrete Distributions using Entropic Independence

Abstract: We present a framework for speeding up the time it takes to sample from discrete distributions D defined over subsets of size k of a ground set of n elements, in the regime where k is much smaller than n. We show that if one has access to estimates of each single element's marginal, then the task of sampling from D can be reduced to sampling from related distributions on size k subsets of a ground set whose size is sublinear in n). The degree of sublinearity is controlled by a parameter of the D called the "entropic independence." This subsampling procedure, which we dub domain sparsification, allows us to pay a one-time cost of estimating the marginals, and in return reduce the amortized cost needed to produce additional samples from D.

https://arxiv.org/abs/2109.06442