Image de couverture de livre

Improved Computational Lower Bound of Estimation for Multi-Frequency Group Synchronization

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteur principal:	Li, Zhangsong
Format:	Preprint
Publié:	2026
Sujets:	Statistics Theory Data Structures and Algorithms Probability 68Q87, 68Q17
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Computational Lower Bounds for Correlated Random Graphs via Algorithmic Contiguity
par: Li, Zhangsong
Publié: (2025)

A computational transition for detecting correlated stochastic block models by low-degree polynomials
par: Chen, Guanyi, et autres
Publié: (2024)

Algorithmic Contiguity from Low-Degree Heuristic II: Predicting Detection-Recovery Gaps
par: Li, Zhangsong
Publié: (2026)

The Algorithmic Phase Transition in Correlated Spiked Models
par: Li, Zhangsong
Publié: (2025)

A Smooth Computational Transition in Tensor PCA
par: Li, Zhangsong
Publié: (2025)

Low-Degree Hardness of Detection for Correlated Erdős-Rényi Graphs
par: Ding, Jian, et autres
Publié: (2023)

Robust random graph matching in Gaussian models via vector approximate message passing
par: Li, Zhangsong
Publié: (2024)

A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation
par: Ding, Jian, et autres
Publié: (2023)

The Umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime
par: Gong, Shuyang, et autres
Publié: (2024)

Robust Algorithms for Finding Cliques in Random Intersection Graphs via Sum-of-Squares
par: Göbel, Andreas, et autres
Publié: (2025)

Private Evolution Converges
par: González, Tomás, et autres
Publié: (2025)

A Polynomial-time Algorithm to Solve the Airplane Refueling Problem: the Sequential Search Algorithm
par: Cui, Jinchuan, et autres
Publié: (2022)

Hamiltonicity Parameterized by Mim-Width is (Indeed) Para-NP-Hard
par: Bergougnoux, Benjamin, et autres
Publié: (2025)

The Kikuchi Hierarchy and Tensor PCA
par: Wein, Alexander S., et autres
Publié: (2019)

Computing the probability of intersection
par: Barvinok, Alexander
Publié: (2025)

Algorithmic Universality, Low-Degree Polynomials, and Max-Cut in Sparse Random Graphs
par: Cheairi, Houssam El, et autres
Publié: (2024)

Algorithms for Minimum Membership Dominating Set Problem
par: Reddy, Sangam Balchandar, et autres
Publié: (2024)

Polynomial Identity Testing via Evaluation of Rational Functions
par: Hu, Ivan, et autres
Publié: (2022)

Spectral Shadows: When Communication Complexity Meets Linear Invariance Testing
par: Datta, Swarnalipa, et autres
Publié: (2026)

Optimal rolling of fair dice using fair coins
par: Huber, Mark, et autres
Publié: (2024)

Efficient Algorithms for Injectivity and Bounded Surjectivity of One-dimensional Nonlinear Cellular Automata
par: Wang, Chen, et autres
Publié: (2023)

Optimal Hardness of Online Algorithms for Large Independent Sets
par: Gamarnik, David, et autres
Publié: (2025)

Information-Theoretic Thresholds for Bipartite Latent-Space Graphs under Noisy Observations
par: Göbel, Andreas, et autres
Publié: (2026)

Probabilistic Computers (So Quantum Computers) Are More Rigorously Powerful Than Traditional Computers, and Derandomization
par: Lin, Tianrong
Publié: (2023)

Binary Tree Block Encoding of Classical Matrix
par: Li, Zexian, et autres
Publié: (2025)

Ineffectiveness for Search and Undecidability of PCSP Meta-Problems
par: Larrauri, Alberto
Publié: (2025)

Treewidth Inapproximability and Tight ETH Lower Bound
par: Bonnet, Édouard
Publié: (2024)

Parameterized Complexity of Directed Traveling Salesman Problem
par: Blažej, Václav, et autres
Publié: (2025)

Computational barriers for permutation-based problems, and cumulants of weakly dependent random variables
par: Even, Bertrand, et autres
Publié: (2025)

Analysis of multivariate symbol statistics in primitive rational models
par: Goldwurm, Massimiliano, et autres
Publié: (2026)

Simple Combinatorial Construction of the $k^{o(1)}$-Lower Bound for Approximating the Parameterized $k$-Clique
par: Chen, Yijia, et autres
Publié: (2023)

Statistical-Computational Trade-offs for Recursive Adaptive Partitioning Estimators
par: Tan, Yan Shuo, et autres
Publié: (2024)

Fast sampling of satisfying assignments from random $k$-SAT with applications to connectivity
par: Chen, Zongchen, et autres
Publié: (2022)

Parallel Algorithms for Group Isomorphism via Code Equivalence
par: Levet, Michael
Publié: (2026)

On weighted graph separation problems and flow-augmentation
par: Kim, Eun Jung, et autres
Publié: (2022)

Fine-Grained Complexity of Computing Degree-Constrained Spanning Trees
par: Bojikian, Narek, et autres
Publié: (2025)

A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
par: Jiang, Xinwen, et autres
Publié: (2021)

Approximation and generalization properties of the random projection classification method
par: Boutin, Mireille, et autres
Publié: (2021)

Coordinatewise Balanced Covering for Linear Gain Graphs, with an Application to Coset-List Min-2-Lin over Powers of Two
par: Alpay, Faruk, et autres
Publié: (2026)

A Proof of The Changepoint Detection Threshold Conjecture in Preferential Attachment Models
par: Du, Hang, et autres
Publié: (2025)