21 citations · 129 across the 21 of their papers we have counts for
24 papers
Sharp detection thresholds for random geometric graphs with polynomial average degrees
Hang Du, Cheng Mao, Nike Sun +2
We study the random geometric graph formed by connecting independent uniform points on whenever their inner product exceeds a threshold chosen to give edge de…
Recovery of latent inner products from an anisotropic Gaussian random geometric graph
Cheng Mao, Vidya Muthukumar
We study the problem of recovering latent inner products from a random geometric graph with anisotropic Gaussian latent points. More precisely, for an i.i.d. sample $x_1, \dots, x_…
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…
Resolution of the Detection Threshold Conjecture for Random Geometric Graphs in the Regime
Hang Du, Cheng Mao, Nike Sun +2
A random geometric graph (RGG) is generated by first sampling latent points independently and uniformly from the unit sphere in , and then connecting…
Detection of Dense Subhypergraphs by Low-Degree Polynomials
Abhishek Dhawan, Cheng Mao, Alexander S. Wein
Detection of a planted dense subgraph in a random graph is a fundamental statistical and computational problem that has been extensively studied in recent years. We study a hypergr…
Sharp analysis of EM for learning mixtures of pairwise differences
Abhishek Dhawan, Cheng Mao, Ashwin Pananjady
We consider a symmetric mixture of linear regressions with random samples from the pairwise comparison design, which can be seen as a noisy version of a type of Euclidean distance…
Detection-Recovery Gap for Planted Dense Cycles
Cheng Mao, Alexander S. Wein, Shenduo Zhang
Planted dense cycles are a type of latent structure that appears in many applications, such as small-world networks in social sciences and sequence assembly in computational biolog…
Random graph matching at Otter's threshold via counting chandeliers
Cheng Mao, Yihong Wu, Jiaming Xu +1
We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős-Ré…
Testing network correlation efficiently via counting trees
Cheng Mao, Yihong Wu, Jiaming Xu +1
We propose a new procedure for testing whether two networks are edge-correlated through some latent vertex correspondence. The test statistic is based on counting the co-occurrence…
Exact Matching of Random Graphs with Constant Correlation
Cheng Mao, Mark Rudelson, Konstantin Tikhomirov
This paper deals with the problem of graph matching or network alignment for Erdős--Rényi graphs, which can be viewed as a noisy average-case version of the graph isomorphism probl…
Optimal Spectral Recovery of a Planted Vector in a Subspace
Cheng Mao, Alexander S. Wein
Recovering a planted vector in an -dimensional random subspace of is a generic task related to many problems in machine learning and statistics, such as dicti…
Random Graph Matching with Improved Noise Robustness
Cheng Mao, Mark Rudelson, Konstantin Tikhomirov
Graph matching, also known as network alignment, refers to finding a bijection between the vertex sets of two given graphs so as to maximally align their edges. This fundamental co…
Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments
Cheng Mao, Yihong Wu
In applications such as rank aggregation, mixture models for permutations are frequently used when the population exhibits heterogeneity. In this work, we study the widely used Mal…
Optimal Rates for Estimation of Two-Dimensional Totally Positive Distributions
Jan-Christian Hütter, Cheng Mao, Philippe Rigollet +1
We study minimax estimation of two-dimensional totally positive distributions. Such distributions pertain to pairs of strongly positively dependent random variables and appear freq…
Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
Zhou Fan, Cheng Mao, Yihong Wu +1
We analyze a new spectral graph matching algorithm, GRAph Matching by Pairwise eigen-Alignments (GRAMPA), for recovering the latent vertex correspondence between two unlabeled, edg…
Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
Zhou Fan, Cheng Mao, Yihong Wu +1
Graph matching aims at finding the vertex correspondence between two unlabeled graphs that maximizes the total edge weight correlation. This amounts to solving a computationally in…
Estimation of Monge Matrices
Jan-Christian Hütter, Cheng Mao, Philippe Rigollet +1
Monge matrices and their permuted versions known as pre-Monge matrices naturally appear in many domains across science and engineering. While the rich structural properties of such…
Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
Cheng Mao, Ashwin Pananjady, Martin J. Wainwright
Many applications, including rank aggregation, crowd-labeling, and graphon estimation, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on it…
Breaking the Barrier: Faster Rates for Permutation-based Models in Polynomial Time
Cheng Mao, Ashwin Pananjady, Martin J. Wainwright
Many applications, including rank aggregation and crowd-labeling, can be modeled in terms of a bivariate isotonic matrix with unknown permutations acting on its rows and columns. W…
Minimax Rates and Efficient Algorithms for Noisy Sorting
Cheng Mao, Jonathan Weed, Philippe Rigollet
There has been a recent surge of interest in studying permutation-based models for ranking from pairwise comparison data. Despite being structurally richer and more robust than par…
Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
Ashwin Pananjady, Cheng Mao, Vidya Muthukumar +2
Pairwise comparison data arises in many domains, including tournament rankings, web search, and preference elicitation. Given noisy comparisons of a fixed subset of pairs of items,…
Optimal Rates of Statistical Seriation
Nicolas Flammarion, Cheng Mao, Philippe Rigollet
Given a matrix the seriation problem consists in permuting its rows in such way that all its columns have the same shape, for example, they are monotone increasing. We propose a st…
Inventory Accumulation with Products
Cheng Mao, Tianyou Zhou
Sheffield (2011) proposed an inventory accumulation model with two types of products to study the critical Fortuin-Kasteleyn model on a random planar map, and showed that a two-dim…
Scaling limits for the critical Fortuin-Kasteleyn model on a random planar map I: cone times
Ewain Gwynne, Cheng Mao, Xin Sun
Sheffield (2011) introduced an inventory accumulation model which encodes a random planar map decorated by a collection of loops sampled from the critical Fortuin-Kasteleyn (FK) mo…