6 papers
Computational Thresholds for Balanced and Fixed-Slice Independent Sets in Bipartite Graphs
Ijay Narang, Will Perkins, Yuzhou Wang +1
Motivated by recent work of Kocurek, Oveis Gharan, and Tjowasi, which gives an efficient sampling algorithm for the hard-core model on random regular bipartite graphs by decomposin…
Geometric planted matchings in high dimensions: The power of multiple views
Timothy L. H. Wee, Kaylee Y. Yang, Zhou Fan +1
We study the problem of recovering the correspondence between a collection of points in and a noisy, permuted version of those points. In the high-dimensional re…
Bayesian inference of planted matchings: Local posterior approximation and infinite-volume limit
Zhou Fan, Timothy L. H. Wee, Kaylee Y. Yang
We study Bayesian inference of an unknown matching between two correlated random point sets and in , under a critical scaling $\…
Optimal detection of planted stars via a random energy model
Ijay Narang, Will Perkins, Timothy L. H. Wee
We study the problem of detecting a planted star in the Erd{Å}s--R{é}nyi random graph , formulated as a hypothesis test. We determine the scaling window for critical dete…
Cluster expansion of the log-likelihood ratio: Optimal detection of planted matchings
Timothy L. H. Wee, Cheng Mao
To understand how hidden information can be extracted from statistical networks, planted models in random graphs have been the focus of intensive study in recent years. In this wor…
Asymptotic mutual information in quadratic estimation problems over compact groups
Kaylee Y. Yang, Timothy L. H. Wee, Zhou Fan
Motivated by applications to group synchronization and quadratic assignment on random data, we study a general problem of Bayesian inference of an unknown ``signal'' belonging to a…