8 citations · 12 across the 11 of their papers we have counts for
12 papers
Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
Sitan Chen, Jingqiu Ding, Mahbod Majid +1
Bayesian methods lie at the heart of modern data science and provide a powerful scaffolding for estimation in data-constrained settings and principled quantification and propagatio…
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…
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 …
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…
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, inhomoge…
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…
Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
Rares-Darius Buhai, Jingqiu Ding, Stefan Tiegel
We study computational-statistical gaps for improper learning in sparse linear regression. More specifically, given samples from a -sparse linear model in dimension , we…
Reaching Kesten-Stigum Threshold in the Stochastic Block Model under Node Corruptions
Jingqiu Ding, Tommaso d'Orsi, Yiding Hua +1
We study robust community detection in the context of node-corrupted stochastic block model, where an adversary can arbitrarily modify all the edges incident to a fraction of the $…
SQ Lower Bounds for Random Sparse Planted Vector Problem
Jingqiu Ding, Yiding Hua
Consider the setting where a -sparse Rademacher vector is planted in a random -dimensional subspace of . A classical question is how to recover this planted vector given…
Fast algorithm for overcomplete order-3 tensor decomposition
Jingqiu Ding, Tommaso d'Orsi, Chih-Hung Liu +2
We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to . Our algorithm only involves…
Robust recovery for stochastic block models
Jingqiu Ding, Tommaso d'Orsi, Rajai Nasser +1
We develop an efficient algorithm for weak recovery in a robust version of the stochastic block model. The algorithm matches the statistical guarantees of the best known algorithms…
Estimating Rank-One Spikes from Heavy-Tailed Noise via Self-Avoiding Walks
Jingqiu Ding, Samuel B. Hopkins, David Steurer
We study symmetric spiked matrix models with respect to a general class of noise distributions. Given a rank-1 deformation of a random noise matrix, whose entries are independently…