research
∙
04/17/2023
Detection of Dense Subhypergraphs by Low-Degree Polynomials
Detection of a planted dense subgraph in a random graph is a fundamental...
share
research
∙
02/20/2023
Sharp analysis of EM for learning mixtures of pairwise differences
We consider a symmetric mixture of linear regressions with random sample...
research
∙
02/13/2023
Detection-Recovery Gap for Planted Dense Cycles
Planted dense cycles are a type of latent structure that appears in many...
research
∙
09/25/2022
Random graph matching at Otter's threshold via counting chandeliers
We propose an efficient algorithm for graph matching based on similarity...
research
∙
10/22/2021
Testing network correlation efficiently via counting trees
We propose a new procedure for testing whether two networks are edge-cor...
research
∙
10/11/2021
Exact Matching of Random Graphs with Constant Correlation
This paper deals with the problem of graph matching or network alignment...
research
∙
05/31/2021
Optimal Spectral Recovery of a Planted Vector in a Subspace
Recovering a planted vector v in an n-dimensional random subspace of ℝ^N...
research
∙
01/28/2021
Random Graph Matching with Improved Noise Robustness
Graph matching, also known as network alignment, refers to finding a bij...
research
∙
09/14/2020
Learning Mixtures of Permutations: Groups of Pairwise Comparisons and Combinatorial Method of Moments
In applications such as rank aggregation, mixture models for permutation...
research
∙
06/13/2020
Optimal Rates for Estimation of Two-Dimensional Totally Positive Distributions
We study minimax estimation of two-dimensional totally positive distribu...
research
∙
07/20/2019
Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality
We analyze a new spectral graph matching algorithm, GRAph Matching by Pa...
research
∙
07/20/2019
Spectral Graph Matching and Regularized Quadratic Relaxations I: The Gaussian Model
Graph matching aims at finding the vertex correspondence between two unl...
research
∙
04/05/2019
Estimation of Monge Matrices
Monge matrices and their permuted versions known as pre-Monge matrices n...
research
∙
06/25/2018
Towards Optimal Estimation of Bivariate Isotonic Matrices with Unknown Permutations
Many applications, including rank aggregation, crowd-labeling, and graph...
research
∙
02/27/2018
Breaking the 1/√(n) Barrier: Faster Rates for Permutation-based Models in Polynomial Time
Many applications, including rank aggregation and crowd-labeling, can be...
research
∙
10/28/2017
Minimax Rates and Efficient Algorithms for Noisy Sorting
There has been a recent surge of interest in studying permutation-based ...
research
∙
07/19/2017
Worst-case vs Average-case Design for Estimation from Fixed Pairwise Comparisons
Pairwise comparison data arises in many domains, including tournament ra...
research
∙
07/08/2016