Timothy L.H. Wee

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 decomposing into fixed-size slices, we study the worst-case tractability of approximate counting and sampling of fixed-size slices for bipartite independent set problems. Let \(G=(L⊔R,E)\)be a bipartite graph with \(|L|=|R|=n\)and maximum degree ∆. The fixed-slice problem asks to sample uniformly from independent sets satisfying \(|I∩L|=\alpha_L n\)and \(|I∩R|=\alpha_R n\). We show that if the overall density αlies in the interval (\frac1∆, \tfrac12), and the densities on the two sides are more balanced than the typical phase densities of a random ∆-regular bipartite graph, then there is no FPRAS or efficient sampling scheme unless \mathbfNP=\mathbfRP. We then study a related fugacity model in which the densities are not fixed, but the independent set is required to be balanced between the two sides of the bipartition. For \(λ>0\), the balanced hard-core model is the ordinary hard-core model with fugacity \(λ\), conditioned on the event \(|I∩L|=|I∩R|\). We prove that this model has the same computational threshold as the hard-core model on general bounded-degree graphs. That is, for every fixed \(∆\ge 3\), if \(λ<\lambda_c(∆)\), then the balanced partition function admits an FPTAS and the balanced hard-core distribution admits an efficient sampling scheme. Conversely, if \(λ>\lambda_c(∆)\), then no FPRAS or efficient sampler exists on this graph class unless \mathbfNP=\mathbfRP.

We study the problem of recovering the correspondence between a collection of n points in \mathbbR^d and a noisy, permuted version of those points. In the high-dimensional regime d=ω(\log n), under a Gaussian model with noise variance σ^2=d/(b\log n), prior work identifies b=2 as the threshold for almost exact recovery. We prove that this threshold is all-or-nothing: for every fixed b<2, no estimator recovers a positive fraction of the matching, and even estimating the matched point cloud in Euclidean distance is asymptotically no better than ignoring the correspondence. On the other hand, we consider a multi-view generalization of the problem where K noisy, independently permuted copies of the same latent point cloud are observed. Here we show that a simple polynomial-time procedure recovers all relative matchings up to o(n) errors whenever b>K/(K-1). Thus multiple views can break the impossibility barrier b=2 for the original matching problem: in particular, for 3/2 < b < 2, the two-view model has no nontrivial recovery, but a third view makes all latent correspondences efficiently recoverable.

We study Bayesian inference of an unknown matching \pi^* between two correlated random point sets {X_i}_i=1^n and {Y_i}_i=1^n in [0,1]^d, under a critical scaling \|X_i-Y_\pi^*(i)\|_2 ≍n^-1/d, in both an exact matching model where all points are observed and a partial matching model where a fraction of points may be missing. Restricting to the simplest setting of d=1, in this work, we address the questions of (1) whether the posterior distribution over matchings is approximable by a local algorithm, and (2) whether marginal statistics of this posterior have a well-defined limit as n \to ∞. We answer both questions affirmatively for partial matching, where a decay-of-correlations arises for large n. For exact matching, we show that the posterior is approximable locally only after a global sorting of the points, and that defining a large-n limit of marginal statistics requires a careful indexing of points in the Poisson point process limit of the data, based on a notion of flow. We leave as an open question the extensions of such results to dimensions d ≥2.

We study the problem of detecting a planted star in the Erdős–Rényi random graph G(n,m), formulated as a hypothesis test. We determine the scaling window for critical detection in m in terms of the star size, and characterize the asymptotic total variation distance between the null and alternative hypotheses in this window. In the course of the proofs we show a condensation phase transition in the likelihood ratio that closely resembles that of the random energy model from spin glass theory.

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 work, we consider the detection of a planted matching, i.e., an independent edge set, hidden in an Erdős–Rényi random graph, which is formulated as a hypothesis testing problem. We identify the critical regime for this testing problem and prove that the log-likelihood ratio is asymptotically normal. Via analyses of computationally efficient edge or wedge count test statistics that attain the optimal limits of detection, our results also reveal the absence of a statistical-to-computational gap. Our main technical tool is the cluster expansion from statistical physics, which allows us to prove a precise, non-asymptotic characterization of the log-likelihood ratio. Our analyses rely on a careful reorganization and cancellation of terms that occur in the difference between monomer-dimer log partition functions on the complete and Erdős–Rényi graphs. This combinatorial and statistical physics approach represents a significant departure from the more established methods such as orthogonal decompositions, and positions the cluster expansion as a viable technique in the study of log-likelihood ratios for planted models in general.

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 high-dimensional compact group, given noisy pairwise observations of a featurization of this signal. We establish a quantitative comparison between the signal-observation mutual information in any such problem with that in a simpler model with linear observations, using interpolation methods. For group synchronization, our result proves a replica formula for the asymptotic mutual information and Bayes-optimal mean-squared-error. Via analyses of this replica formula, we show that the conjectural phase transition threshold for computationally-efficient weak recovery of the signal is determined by a classification of the real-irreducible components of the observed group representation(s), and we fully characterize the information-theoretic limits of estimation in the example of angular/phase synchronization over \mathbbSO(2)/\mathbbU(1). For quadratic assignment, we study observations given by a kernel matrix of pairwise similarities and a randomly permutated and noisy counterpart, and we show in a bounded signal-to-noise regime that the asymptotic mutual information coincides with that in a Bayesian spiked model with i.i.d. signal prior.

Define the overlap of a random vector to be its inner product with an independent copy. A random vector whose Euclidean norm and overlap concentrates is shown to have random low-dimensional projections that are approximately random Gaussians. Conversely, asymptotically random Gaussian projections imply these hypotheses. This extends and unites several existing results in geometric functional analysis and spin glasses. Applications include a large-system characterization of the joint law of cavity fields in the Sherrington-Kirkpatrick model.