We study community detection in the \emph{symmetric $k$-stochastic block model}, where $n$ nodes are evenly partitioned into $k$ clusters with intra- and inter-cluster connection probabilities $p$ and $q$, respectively. Our main result is a polynomial-time algorithm that achieves the optimal misclassification rate $\exp(-(1 \pm o(1)) C/k)$, where $C = (\sqrt{pn} - \sqrt{qn})^2$, whenever $C \geq K k^2 \log k$ for some universal constant $K$, matching the Kesten–Stigum ({KS}) threshold up to a $\log k$ factor. Notably, this rate holds even when an adversary corrupts an $\eta \leq \exp(-(1 \pm o(1)) C/k)$ fraction of the nodes. To the best of our knowledge, this optimal error rate was previously only attainable either via computationally inefficient procedures (Zhang and Zhou, 2015) or via polynomial-time algorithms that require strictly stronger assumptions such as $C \geq K k^3$ (Gao et al., 2017). In the node-robust setting, the best known algorithm requires the substantially stronger condition $C \geq K k^{102}$ (Liu and Moitra, 2022). Our results close this gap by providing the first polynomial-time algorithm that achieves the optimal error rate near the {KS} threshold in both settings. Our work has two key technical contributions: (1) we robustify majority voting via the Sum-of-Squares framework, (2) we develop a novel graph bisectioning algorithm via robust majority voting, which allows us to significantly improve the misclassification rate to $1/\mathrm{poly}(k)$ for the initial estimation near the {KS} threshold.

The rapid development of advanced sensing and artificial intelligence technologies, has advanced autonomous driving (AD) systems by providing intelligent route planning decisions. However, how to construct an interpretable and efficient decision-making method that can adapt to various complex driving scenarios has become an important and challenging research topic. In this article, a knowledge graph (KG) for AD systems is constructed based on heterogeneous data such as traffic rules and network information. A deep learning model combining bidirectional long short-term memory and conditional random field is used to achieve joint learning of entity recognition and relationship extraction. In order to make decisions on driving behaviors, this article introduces a deep reinforcement learning framework designed to perform knowledge reasoning over the driving KG, which integrates an integrated reward function and an action dropout mechanism. Experimental comparisons against the other advanced knowledge reasoning algorithms on a practical driving rules dataset validate the effectiveness and advantages of the proposed method, with an overall mean average precision exceeding 94%. The validity of the proposed method has also been verified on the simulation platform in different road scenarios such as multilane, roundabout, intersection and thru-junction.

The effectiveness of existing testing methods is under scrutiny due to significant limitations, notably the discrepancy between action distributions and actual distributions caused by inadequate environmental understanding. Additionally, the lack of a scheme prioritizing fidelity while coordinating testing efficiency results in considerable divergence between test and natural scenarios. To address these issues, this paper proposes a Directed Graph Reinforcement Learning approach with action constraint optimization (DGRL) to generate critical scenarios, balancing efficiency and fidelity. By incorporating directed graph convolutional networks, the model encodes environmental states within the observation interval, providing spatiotemporal insights and reducing action distribution discrepancies. Furthermore, it constructs an unbiased estimation reward considering action constraints by sampling action confidence intervals, filtering out distorted actions, thus balancing efficiency and fidelity. DGRL was trained using the highD dataset, demonstrating robust acceleration performance, with interquartile range ($IQR$) of 3.1 and first quartile ($Q_{1}$) of 75.6 in the acceleration ratio distribution, representing the bandwidth and baseline, respectively. The model also achieved high fidelity, with scenario discrepancies compared to natural scenarios reduced by 85.4% ($Q_{1}$) and 46.5% ($IQR$) relative to GAIL, which considers the rationality of driving behavior. Here,$Q_{1}$represents the baseline of scenario discrepancy, and$IQR$denotes the distribution bandwidth of scenario discrepancy. Additionally, there was 69.7% reduction in the upper limit of the 95% confidence interval, indicating a significant decrease in maximum scenario discrepancy. Deployment on an intelligent connected hardware-in-the-loop testing platform validated DGRL’s effectiveness and applicability in real-world.

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.

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.

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].

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).

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 number of blocks. The statistical utility guarantees match those of the previous best information-theoretic (exponential-time) node-private mechanisms for these problems. The algorithm is based on an exponential mech- anism for a score function defined in terms of a sum-of-squares relaxation whose level depends on the number of blocks. The key ingredients of our results are (1) a characterization of the distance between the block graphons in terms of a quadratic optimization over the polytope of doubly stochastic matrices, (2) a general sum-of-squares convergence result for polynomial op- timization over arbitrary polytopes, and (3) a general approach to perform Lipschitz extensions of score functions as part of the sum-of-squares algorithmic paradigm.

Consider the setting where a $\rho$-sparse Rademacher vector is planted in a random $d$-dimensional subspace of $R^n$. A classical question is how to recover this planted vector given a random basis in this subspace. A recent result by Zadik et al. showed that the Lattice basis reduction algorithm can recover the planted vector when $n\geq d+1$ (Zadik et al. (2021)). Although the algorithm is not expected to tolerate inverse polynomial amount of noise, it is surprising because it was previously shown that recovery cannot be achieved by low degree polynomials when $n \ll \rho^2 d^{2}$ (Mao and Wein (2021)). A natural question is whether we can derive an Statistical Query (SQ) lower bound matching the previous low degree lower bound in Mao and Wein (2021). This will (1) imply that the SQ lower bound can be surpassed by lattice based algorithms; (2) predict the computational hardness when the planted vector is perturbed by inverse polynomial amount of noise. In this paper, we prove such an SQ lower bound. In particular, we show that super-polynomial number of VSTAT queries is needed to solve the easier statistical testing problem when $n \ll \rho^2 d^{2}$ and $\rho \gg \frac{1}{\sqrt{d}}$. The most notable technique we used to derive the SQ lower bound is the almost equivalence relationship between SQ lower bound and low degree lower bound (Brennan et al. (2020); Mao and Wein (2021)).

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 n vertices. We present the first polynomial-time algorithm that achieves weak recovery at the Kesten-Stigum threshold even in the presence of a small constant fraction of corrupted nodes. Prior to this work, even state-of-the-art robust algorithms were known to break under such node corruption adversaries, when close to the Kesten-Stigum threshold.We further extend our techniques to the $Z_2$ synchronization problem, where our algorithm reaches the optimal recovery threshold in the presence of similar strong adversarial perturbations.The key ingredient of our algorithm is a novel identifiability proof that leverages the push-out effect of the Grothendieck norm of principal submatrices.

Decentralization promises to remedy the drawbacks of the web by executing decentralized applications (DApps) on blockchains. Unfortunately, modern blockchains cannot support realistic web application workloads mainly due to congestion.We introduce the Smart Redbelly Blockchain (SRBB), a provably correct permissionless blockchain that reduces congestion by (1) avoiding redundant propagation and validations of transactions with Transaction Validation and Propagation Reduction (TVPR) and (2) mitigating the propagation of invalid transactions within blocks by Byzantine nodes with a dedicated Reward-Penalty Mechanism (RPM). Our comparison of SRBB against Algorand, Avalanche, Diem, Ethereum, Quorum, and Solana, using the DIABLO benchmark suite, indicates that SRBB outperforms all these blockchains under real application workloads. Moreover, SRBB is the only blockchain to successfully execute real workloads of NASDAQ and Uber on a DApp without losing transactions. To demonstrate that TVPR and RPM are the causes of the improved performance, we compare SRBB with its naive baseline, which does not contain TVPR and RPM. Our results show that TVPR increases the throughput by 55× and divides the latency by 3.5, while RPM increases the throughput by 7% under flooding attacks. Finally, TVPR helps reduce transaction losses in the normal scenario while RPM goes further and mitigates transaction losses under flooding attacks.

In this article, we show that the algorithm of maintaining expander decompositions in graphs undergoing edge deletions directly by removing sparse cuts repeatedly can be made efficient. Formally, for an m-edge undirected graph G, we say a cut is ϕ-sparse if . A ϕ-expander decomposition of G is a partition of V into sets X1,X2,…, Xk such that each cluster G[X1] contains no ϕ-sparse cut (meaning it is a ϕ-expander) with Õ(ϕm) edges crossing between clusters. A natural way to compute a ϕ-expander decomposition is to decompose clusters by ϕ-sparse cuts until no such cut is contained in any cluster. We show that even in graphs undergoing edge deletions, a slight relaxation of this meta-algorithm can be implemented efficiently with amortized update time mo(1)/ϕ2. Our approach naturally extends to maintaining directed ϕ-expander decompositions and ϕ-expander hierarchies and thus gives a unifying framework while having simpler proofs than previous state-of-the-art work. In all settings, our algorithm matches the run-times of previous algorithms up to subpolynomial factors. Moreover, our algorithm provides stronger guarantees for ϕ-expander decompositions. For example, for graphs undergoing edge deletions, our approach is the first to maintain a dynamic expander decomposition where each updated decomposition is a refinement of the previous decomposition, and our approach is the first to guarantee a sublinear ϕm1+ο(1) bound on the total number of edges that cross between clusters across the entire sequence of dynamic updates. Our techniques also give by far the simplest, deterministic algorithms for maintaining Strongly-Connected Components (SCCs) in directed graphs undergoing edge deletions, and for maintaining connectivity in undirected fully-dynamic graphs, both matching the current state-of-the art run-times up to subpolynomial factors. * The full version of the paper can be accessed at https://arxiv.org/abs/2204.02519