6 papers
Rate-optimal community detection near the KS threshold via node-robust algorithms
Jingqiu Ding, Yiding Hua, Kasper Lindberg +2
We study community detection in the \emph{symmetric -stochastic block model}, where nodes are evenly partitioned into clusters with intra- and inter-cluster connection p…
Finding Colorings in One-Sided Expanders
Rares-Darius Buhai, Yiding Hua, David Steurer +1
We establish new algorithmic guarantees with matching hardness results for coloring and independent set problems in one-sided expanders and related classes of graphs. For example,…
Low degree conjecture implies sharp computational thresholds in stochastic block model
Jingqiu Ding, Yiding Hua, Lucas Slot +1
We investigate implications of the (extended) low-degree conjecture (recently formalized in [MW23]) in the context of the symmetric stochastic block model. Assuming the conjecture…
Improved Robust Estimation for ErdÅs-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point
Hongjie Chen, Jingqiu Ding, Yiding Hua +1
We study the problem of robustly estimating the edge density of ErdÅs-Rényi random graphs when an adversary can arbitrarily add or remove edges incident to an $…
Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
Hongjie Chen, Jingqiu Ding, Yiding Hua +1
We give the first polynomial-time, differentially node-private, and robust algorithm for estimating the edge density of ErdÅs-Rényi random graphs and their generalization, inhomo…
Private graphon estimation via sum-of-squares
Hongjie Chen, Jingqiu Ding, Tommaso d'Orsi +3
We develop the first pure node-differentially-private algorithms for learning stochastic block models and for graphon estimation with polynomial running time for any constant numbe…