Buchumschlag

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Li, Zhangsong
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Machine Learning Data Structures and Algorithms Probability Statistics Theory 68Q87, 68Q17
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

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

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

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

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)

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

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

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

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

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

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

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
von: Cui, Jinchuan, et al.
Veröffentlicht: (2022)

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

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

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

Algorithms for Minimum Membership Dominating Set Problem
von: Reddy, Sangam Balchandar, et al.
Veröffentlicht: (2024)

Polynomial Identity Testing via Evaluation of Rational Functions
von: Hu, Ivan, et al.
Veröffentlicht: (2022)

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

Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
von: Wang, Chen, et al.
Veröffentlicht: (2023)

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

Approximation and generalization properties of the random projection classification method
von: Boutin, Mireille, et al.
Veröffentlicht: (2021)

A Randomized Algorithm for Preconditioner Selection
von: DiPaolo, Conner, et al.
Veröffentlicht: (2019)

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
von: Datta, Swarnalipa, et al.
Veröffentlicht: (2026)

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

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

Algorithms for Generating Small Random Samples
von: Cicirello, Vincent A.
Veröffentlicht: (2024)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
von: Lin, Tianrong
Veröffentlicht: (2023)

Binary Tree Block Encoding of Classical Matrix
von: Li, Zexian, et al.
Veröffentlicht: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
von: Larrauri, Alberto
Veröffentlicht: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
von: Bonnet, Édouard
Veröffentlicht: (2024)

On the Average Runtime of an Open Source Binomial Random Variate Generation Algorithm
von: Cicirello, Vincent A.
Veröffentlicht: (2024)

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

Parameterized Complexity of Directed Traveling Salesman Problem
von: Blažej, Václav, et al.
Veröffentlicht: (2025)

Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
von: Even, Bertrand, et al.
Veröffentlicht: (2025)

Analysis of multivariate symbol statistics in primitive rational models
von: Goldwurm, Massimiliano, et al.
Veröffentlicht: (2026)

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

A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
von: Jiang, Xinwen, et al.
Veröffentlicht: (2021)

Parallel Algorithms for Group Isomorphism via Code Equivalence
von: Levet, Michael
Veröffentlicht: (2026)

Parameterized Algorithms for Kidney Exchange
von: Maiti, Arnab, et al.
Veröffentlicht: (2021)