Buchumschlag

Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ding, Jian, Du, Hang, Li, Zhangsong
Format:	Preprint
Veröffentlicht:	2023
Schlagworte:	Data Structures and Algorithms Probability Statistics Theory 68Q87, 62M20
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

A computational transition for detecting correlated stochastic block models by low-degree polynomials
von: Chen, Guanyi, et al.
Veröffentlicht: (2024)

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
von: Li, Zhangsong
Veröffentlicht: (2025)

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization
von: Li, Zhangsong
Veröffentlicht: (2026)

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

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
von: Li, Zhangsong
Veröffentlicht: (2026)

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

A Smooth Computational Transition in Tensor PCA
von: Li, Zhangsong
Veröffentlicht: (2025)

Robust random graph matching in Gaussian models via vector approximate message passing
von: Li, Zhangsong
Veröffentlicht: (2024)

The Algorithmic Phase Transition in Correlated Spiked Models
von: Li, Zhangsong
Veröffentlicht: (2025)

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

Detecting Correlation Efficiently in Stochastic Block Models: Breaking Otter's Threshold in the Entire Supercritical Regime
von: Chen, Guanyi, et al.
Veröffentlicht: (2025)

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

A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation
von: Ding, Jian, et al.
Veröffentlicht: (2022)

The Kikuchi Hierarchy and Tensor PCA
von: Wein, Alexander S., et al.
Veröffentlicht: (2019)

Private Evolution Converges
von: González, Tomás, et al.
Veröffentlicht: (2025)

Fundamental Limits of Community Detection in Contextual Multi-Layer Stochastic Block Models
von: Gong, Shuyang, et al.
Veröffentlicht: (2026)

Strong Low Degree Hardness for the Number Partitioning Problem
von: Mallarapu, Rushil, et al.
Veröffentlicht: (2025)

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

Statistical-Computational Trade-offs for Recursive Adaptive Partitioning Estimators
von: Tan, Yan Shuo, et al.
Veröffentlicht: (2024)

Computing the probability of intersection
von: Barvinok, Alexander
Veröffentlicht: (2025)

Optimal rolling of fair dice using fair coins
von: Huber, Mark, et al.
Veröffentlicht: (2024)

Faster algorithms for the alignment of sparse correlated Erdös-Rényi random graphs
von: Muratori, Andrea, et al.
Veröffentlicht: (2024)

A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
von: Du, Hang, et al.
Veröffentlicht: (2025)

Optimal Hardness of Online Algorithms for Large Independent Sets
von: Gamarnik, David, et al.
Veröffentlicht: (2025)

Stochastic gradient descent in high dimensions for multi-spiked tensor PCA
von: Arous, Gérard Ben, et al.
Veröffentlicht: (2024)

Information-Theoretic Thresholds for Bipartite Latent-Space Graphs under Noisy Observations
von: Göbel, Andreas, et al.
Veröffentlicht: (2026)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
von: Sohn, Youngtak, et al.
Veröffentlicht: (2025)

Kantorovich Distance via Spanning Trees: Properties and Algorithms
von: Bigot, Jérémie, et al.
Veröffentlicht: (2026)

Fast sampling of satisfying assignments from random $k$-SAT with applications to connectivity
von: Chen, Zongchen, et al.
Veröffentlicht: (2022)

Fast Dimensionality Reduction from $\ell_2$ to $\ell_p$
von: Chiclana, Rafael, et al.
Veröffentlicht: (2025)

On Extended Concentration Inequalities for Fast JL Embeddings of Infinite Sets
von: Boahen, Edem, et al.
Veröffentlicht: (2025)

Random Multi-Type Spanning Forests for Synchronization on Sparse Graphs
von: Jaquard, Hugo, et al.
Veröffentlicht: (2024)

On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
von: Chen, Zongchen, et al.
Veröffentlicht: (2024)

A Method for Generating Connected Erdos-Renyi Random Graphs
von: Chinyaev, Boris
Veröffentlicht: (2025)

The Breakdown of Gaussian Universality in Classification of High-dimensional Linear Factor Mixtures
von: Mai, Xiaoyi, et al.
Veröffentlicht: (2024)

Improved Randomized Approximation of Hard Universality and Emptiness Problems
von: Andreou, Pantelis, et al.
Veröffentlicht: (2024)

Efficiently matching random inhomogeneous graphs via degree profiles
von: Ding, Jian, et al.
Veröffentlicht: (2023)

Langevin dynamics for high-dimensional optimization: the case of multi-spiked tensor PCA
von: Arous, Gérard Ben, et al.
Veröffentlicht: (2024)

Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection
von: Morgan, Alexander, et al.
Veröffentlicht: (2026)

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