Copertina

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autore principale:	Li, Zhangsong
Natura:	Preprint
Pubblicazione:	2026
Soggetti:	Statistics Theory Data Structures and Algorithms Machine Learning Primary 68Q87, 68Q17, Secondary 62F15
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

The Algorithmic Phase Transition in Correlated Spiked Models
di: Li, Zhangsong
Pubblicazione: (2025)

A Smooth Computational Transition in Tensor PCA
di: Li, Zhangsong
Pubblicazione: (2025)

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

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

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

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

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

The Kikuchi Hierarchy and Tensor PCA
di: Wein, Alexander S., et al.
Pubblicazione: (2019)

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

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

Leakage-Resilient Hardness Equivalence to Logspace Derandomization
di: Shalunov, Yakov
Pubblicazione: (2023)

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

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

Quantum Search without Global Diffusion
di: Burke, John, et al.
Pubblicazione: (2026)

Conformal e-prediction in the presence of confounding
di: Vovk, Vladimir, et al.
Pubblicazione: (2026)

Universality of conformal prediction under the assumption of randomness
di: Vovk, Vladimir
Pubblicazione: (2025)

A Randomized Algorithm for Preconditioner Selection
di: DiPaolo, Conner, et al.
Pubblicazione: (2019)

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

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
di: Bojikian, Narek, et al.
Pubblicazione: (2025)

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

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

A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
di: Jiang, Xinwen, et al.
Pubblicazione: (2021)

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

On weighted graph separation problems and flow-augmentation
di: Kim, Eun Jung, et al.
Pubblicazione: (2022)

Probabilistic Analysis of Edge Elimination for Euclidean TSP
di: Zhong, Xianghui
Pubblicazione: (2018)

Conformal e-testing
di: Vovk, Vladimir, et al.
Pubblicazione: (2020)

Computational Complexity of Determining the Assembly Index
di: Masierak, Piotr
Pubblicazione: (2026)

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

P not equal to NP
di: Delgado, Daniel Cardona
Pubblicazione: (2023)

Sample completion, structured correlation, and Netflix problems
di: Coregliano, Leonardo N., et al.
Pubblicazione: (2025)

Computing the probability of intersection
di: Barvinok, Alexander
Pubblicazione: (2025)

Randomness, exchangeability, and conformal prediction
di: Vovk, Vladimir
Pubblicazione: (2025)

Parallel Algorithms for Group Isomorphism via Code Equivalence
di: Levet, Michael
Pubblicazione: (2026)

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

Statistical-Computational Trade-offs for Recursive Adaptive Partitioning Estimators
di: Tan, Yan Shuo, et al.
Pubblicazione: (2024)