Cover Image

A computational transition for detecting correlated stochastic block models by low-degree polynomials

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Chen, Guanyi, Ding, Jian, Gong, Shuyang, Li, Zhangsong
Format:	Preprint
Published:	2024
Subjects:	Probability Data Structures and Algorithms Machine Learning Statistics Theory Primary 62M20, Secondary 68Q87, 68Q17
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
by: Gong, Shuyang, et al.
Published: (2024)

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
by: Li, Zhangsong
Published: (2026)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
by: Li, Zhangsong
Published: (2026)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
by: Li, Zhangsong
Published: (2025)

Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
by: Ding, Jian, et al.
Published: (2023)

A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation
by: Ding, Jian, et al.
Published: (2023)

The Algorithmic Phase Transition in Correlated Spiked Models
by: Li, Zhangsong
Published: (2025)

Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
by: Gong, Shuyang, et al.
Published: (2026)

A Smooth Computational Transition in Tensor PCA
by: Li, Zhangsong
Published: (2025)

Robust random graph matching in Gaussian models via vector approximate message passing
by: Li, Zhangsong
Published: (2024)

Private Evolution Converges
by: González, Tomás, et al.
Published: (2025)

A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
by: Du, Hang, et al.
Published: (2025)

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
by: Göbel, Andreas, et al.
Published: (2025)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
by: Bergougnoux, Benjamin, et al.
Published: (2025)

Polynomial Identity Testing via Evaluation of Rational Functions
by: Hu, Ivan, et al.
Published: (2022)

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
by: Cui, Jinchuan, et al.
Published: (2022)

P not equal to NP
by: Delgado, Daniel Cardona
Published: (2023)

Potential Hessian Ascent III: Sampling the Sherrington--Kirkpatrick Model at Beta < 1/2
by: Davies, Ewan, et al.
Published: (2026)

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
by: Shalunov, Yakov
Published: (2023)

Algorithmic Universality, Low-Degree Polynomials, and Max-Cut in Sparse Random Graphs
by: Cheairi, Houssam El, et al.
Published: (2024)

Extending the Extension: Deterministic Algorithm for Non-monotone Submodular Maximization
by: Buchbinder, Niv, et al.
Published: (2024)

Analysis of multivariate symbol statistics in primitive rational models
by: Goldwurm, Massimiliano, et al.
Published: (2026)

Finding a dense submatrix of a random matrix. Sharp bounds for online algorithms
by: Bhamidi, Shankar, et al.
Published: (2025)

Computing the probability of intersection
by: Barvinok, Alexander
Published: (2025)

An Algorithm to Recover Shredded Random Matrices
by: Atamanchuk, Caelan, et al.
Published: (2023)

Algorithms for Minimum Membership Dominating Set Problem
by: Reddy, Sangam Balchandar, et al.
Published: (2024)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
by: Lin, Tianrong
Published: (2023)

Which exceptional low-dimensional projections of a Gaussian point cloud can be found in polynomial time?
by: Montanari, Andrea, et al.
Published: (2024)

Optimal Hardness of Online Algorithms for Large Independent Sets
by: Gamarnik, David, et al.
Published: (2025)

Critical probabilities for positively associated, finite-range dependent percolation models
by: Köhler-Schindler, Laurin, et al.
Published: (2024)

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
by: Datta, Swarnalipa, et al.
Published: (2026)

Directed Temporal Tree Realization for Periodic Public Transport: Easy and Hard Cases
by: Meusel, Julia, et al.
Published: (2025)

Optimal rolling of fair dice using fair coins
by: Huber, Mark, et al.
Published: (2024)

Quantum Search without Global Diffusion
by: Burke, John, et al.
Published: (2026)

Quantum computing algorithms for inverse problems on graphs and an NP-complete inverse problem
by: Ilmavirta, Joonas, et al.
Published: (2023)

Approximation and generalization properties of the random projection classification method
by: Boutin, Mireille, et al.
Published: (2021)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
by: Larrauri, Alberto
Published: (2025)

The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures
by: Mai, Xiaoyi, et al.
Published: (2024)

Generating DDPM-based Samples from Tilted Distributions
by: Mandal, Himadri, et al.
Published: (2026)

SMB algebras II: On the Constraint Satisfaction Problem over Semilattices of Mal'cev Blocks
by: Marković, Petar, et al.
Published: (2026)