Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Strong recovery of geometric planted matchings


Speaker: Jonathan Niles-Weed, NYU
Location: MSB 2112
Start time: Tue, May 9 2023, 1:10PM

We consider the problem of recovering a hidden matching between two correlated sets of n Gaussian samples in R^d. We analyze the performance of the maximum likelihood estimator, establish thresholds at which the MLE almost perfectly recovers the planted matching, and, in this regime, characterize the number of errors up to sub-polynomial factors. These results extend to the geometric setting a recent line of work on recovering matchings planted in random graphs with independently-weighted edges. Joint work with D. Kunisky (Yale).