Arrow Research search

Author name cluster

Yiding Hua

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers
2 author rows

Possible papers

6

FOCS Conference 2025 Conference Paper

Finding Colorings in One-Sided Expanders

  • Rares-Darius Buhai
  • Yiding Hua
  • David Steurer
  • Andor Vári-Kakas

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, given a 3-colorable regular one-sided expander, we compute in polynomial time either an independent set of relative size at least $\frac{1}{2}-o(1)$ or a proper 3-coloring for all but an $o(1)$ fraction of the vertices, where $o(1)$ stands for a function that tends to 0 with the second largest eigenvalue of the normalized adjacency matrix. This result improves on recent seminal work of Bafna, Hsieh, and Kothari (STOC 2025) developing an algorithm that efficiently finds independent sets of relative size at least 0. 01 in such graphs. We also obtain an efficient 1. 6667-factor approximation algorithm for VERTEX COVER in sufficiently strong regular one-sided expanders, improving over a previous $(2-\varepsilon)$-factor approximation in such graphs for an unspecified constant $\varepsilon\gt 0$. We propose a new stratification of k-COLORING in terms of k-by- k matrices akin to predicate sets for constraint satisfaction problems. We prove that whenever this matrix has repeated rows, the corresponding coloring problem is NP-hard for one-sided expanders under the Unique Games Conjecture. On the other hand, if this matrix has no repeated rows, our algorithms can solve the corresponding coloring problem on one-sided expanders in polynomial time. When this k-by- k matrix has repeated rows, we furthermore characterize the maximum fraction of vertices on which a proper k-coloring can be found by polynomial-time algorithms under the Unique Games Conjecture. As starting point for our algorithmic results, we show a property of graph spectra that, to the best of our knowledge, has not been observed before: The number of negative eigenvalues smaller than $-\tau$ is at most $O\left(1 / \tau^{2}\right)$ times the number of eigenvalues larger than $\tau^{2} / 2$. While this result allows us to bound the number of eigenvalues bounded away from 0 in one-sided spectral expanders, this property alone is insufficient for our algorithmic results. For example, given a one-sided regular expander with a balanced 3 -coloring, we can efficiently find a 3 -coloring for all but a $o(1)$ fraction of vertices. At the same time, if we only know that the graph has a balanced 3 -coloring and a bounded number of significant eigenvalues, it is NP-hard under the Unique Games Conjecture to find a 3 -coloring for all but a 0. 1 fraction of vertices.

Details

NeurIPS Conference 2025 Conference Paper

Improved Robust Estimation for Erdős-Rényi Graphs: The Sparse Regime and Optimal Breakdown Point

  • Hongjie Chen
  • Jingqiu Ding
  • Yiding Hua
  • Stefan Tiegel

We study the problem of robustly estimating the edge density of Erdos Renyi random graphs $\mathbb{G}(n, d^\circ/n)$ when an adversary can arbitrarily add or remove edges incident to an $\eta$-fraction of the nodes. We develop the first polynomial-time algorithm for this problem that estimates $d^\circ$ up to an additive error $O\left({[\sqrt{\log(n) / n} + \eta\sqrt{\log(1/\eta)} ] \cdot \sqrt{d^\circ} + \eta \log(1/\eta)}\right)$. Our error guarantee matches information-theoretic lower bounds up to factors of $\log(1/\eta)$. Moreover, our estimator works for all $d^\circ \geq \Omega(1)$ and achieves optimal breakdown point $\eta = 1/2$. Previous algorithms [Acharya et al 2022, Chen et al 2024], including inefficient ones, incur significantly suboptimal errors. Furthermore, even admitting suboptimal error guarantees, only inefficient algorithms achieve optimal breakdown point. Our algorithm is based on the sum-of-squares (SoS) hierarchy. A key ingredient is to construct constant-degree SoS certificates for concentration of the number of edges incident to small sets in $\mathbb{G}(n, d^\circ/n)$. Crucially, we show that these certificates also exist in the sparse regime, when $d^\circ = o(\log n)$, a regime in which the performance of previous algorithms was significantly suboptimal.

PDF Details

NeurIPS Conference 2025 Conference Paper

Low-degree evidence for computational transition of recovery rate in stochastic block model

  • Jingqiu Ding
  • Yiding Hua
  • Lucas Slot
  • David Steurer

We investigate implications of the (extended) low-degree conjecture (recently formalized in [moitra et al2023]) in the context of the symmetric stochastic block model. Assuming the conjecture holds, we establish that no polynomial-time algorithm can weakly recover community labels below the Kesten-Stigum (KS) threshold. In particular, we rule out polynomial-time estimators that, with constant probability, achieve $n^{-0. 49}$ correlation with the true communities. Whereas, above the KS threshold, polynomial-time algorithms are known to achieve constant correlation with the true communities with high probability [massoulie et al 2014, abbe et al 2015]. To our knowledge, we provide the first rigorous evidence for such sharp transition in recovery rate for polynomial-time algorithms at the KS threshold. Notably, under a stronger version of the low-degree conjecture, our lower bound remains valid even when the number of blocks diverges. Furthermore, our results provide evidence of a computational-to-statistical gap in learning the parameters of stochastic block models. In contrast, prior work either (i) rules out polynomial-time algorithms with $1 - o(1)$ success probability [Hopkins 18, bandeira et al 2021] under the low-degree conjecture, or (ii) degree-$\text{poly}(k)$ polynomials for learning the stochastic block model [Luo et al 2023]. For this, we design a hypothesis test which succeeeds with constant probability under symmetric stochastic block model, and $1-o(1)$ probability under the distribution of \Erdos \Renyi random graphs. Our proof combines low-degree lower bounds from [Hopkins 18, bandeira et al 2021] with graph splitting and cross-validation techniques. In order to rule out general recovery algorithms, we employ the correlation preserving projection method developed in [Hopkins et al 17].

PDF Details

NeurIPS Conference 2024 Conference Paper

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust

  • Hongjie Chen
  • Jingqiu Ding
  • Yiding Hua
  • David Steurer

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, inhomogeneous random graphs. We further prove information-theoretical lower bounds, showing that the error rate of our algorithm is optimal up to logarithmic factors. Previous algorithms incur either exponential running time or suboptimal error rates. Two key ingredients of our algorithm are (1) a new sum-of-squares algorithm for robust edge density estimation, and (2) the reduction from privacy to robustness based on sum-of-squares exponential mechanisms due to Hopkins et al. (STOC 2023).

PDF Details DOI