Copertina

Computational lower bounds for multi-frequency group synchronization

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Kireeva, Anastasia, Bandeira, Afonso S., Kunisky, Dmitriy
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Statistics Theory Computational Complexity Probability
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Inference of rankings planted in random tournaments
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Tensor cumulants for statistical inference on invariant distributions
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Statistical inference of a ranked community in a directed graph
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Computational and statistical lower bounds for low-rank estimation under general inhomogeneous noise
di: De, Debsurya, et al.
Pubblicazione: (2025)

Computational hardness of detecting graph lifts and certifying lift-monotone properties of random regular graphs
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2024)

Randomstrasse101: Open Problems of 2024
di: Bandeira, Afonso S., et al.
Pubblicazione: (2025)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
di: Kunisky, Dmitriy, et al.
Pubblicazione: (2022)

Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
di: Kunisky, Dmitriy
Pubblicazione: (2024)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
di: Gamarnik, David, et al.
Pubblicazione: (2023)

Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
di: Kunisky, Dmitriy
Pubblicazione: (2024)

Universal entrywise eigenvector fluctuations in delocalized spiked matrix models and asymptotics of rounded spectral algorithms
di: Chen, Shujing, et al.
Pubblicazione: (2025)

Average-case complexity in statistical inference: A puzzle-driven research seminar
di: Kireeva, Anastasia, et al.
Pubblicazione: (2025)

Nonlinear Laplacians: Tunable principal component analysis under directional prior information
di: Ma, Yuxin, et al.
Pubblicazione: (2025)

Fitting an ellipsoid to random points: predictions using the replica method
di: Maillard, Antoine, et al.
Pubblicazione: (2023)

Symmetric Perceptrons, Number Partitioning and Lattices
di: Vafa, Neekon, et al.
Pubblicazione: (2025)

Average-Case Reductions for $k$-XOR and Tensor PCA
di: Bresler, Guy, et al.
Pubblicazione: (2026)

The Lovász number of random circulant graphs
di: Bandeira, Afonso S., et al.
Pubblicazione: (2025)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
di: Fu, Daniel, et al.
Pubblicazione: (2026)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
di: R., Abhishek Hegade K., et al.
Pubblicazione: (2025)

Testing Convex Truncation
di: De, Anindya, et al.
Pubblicazione: (2023)

Strong Low Degree Hardness for the Number Partitioning Problem
di: Mallarapu, Rushil, et al.
Pubblicazione: (2025)

Sharp Phase Transitions in Estimation with Low-Degree Polynomials
di: Sohn, Youngtak, et al.
Pubblicazione: (2025)

The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
di: Tsirkas, Konstantinos, et al.
Pubblicazione: (2026)

Random Matrices, Intrinsic Freeness, and Sharp Non-Asymptotic Inequalities
di: Bandeira, Afonso S.
Pubblicazione: (2025)

The stochastic block model has the overlap graph property for modularity
di: Bhamidi, Shankar, et al.
Pubblicazione: (2026)

Universality of first-order methods on random and deterministic matrices
di: Gorini, Nicola, et al.
Pubblicazione: (2026)

Detection of local geometry in random graphs: information-theoretic and computational limits
di: Bok, Jinho, et al.
Pubblicazione: (2026)

Matrix Chaos Inequalities and Chaos of Combinatorial Type
di: Bandeira, Afonso S., et al.
Pubblicazione: (2024)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
di: Tang, Runshi, et al.
Pubblicazione: (2026)

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
di: Bresler, Guy, et al.
Pubblicazione: (2025)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
di: Chen, Zherui, et al.
Pubblicazione: (2024)

Approximate Computation via Le Cam Simulability
di: Akdemir, Deniz
Pubblicazione: (2025)

A Geometric Perspective on the Injective Norm of Sums of Random Tensors
di: Bandeira, Afonso S., et al.
Pubblicazione: (2024)

Turing in the shadows of Nobel and Abel: an algorithmic story behind two recent prizes
di: Gamarnik, David
Pubblicazione: (2025)

Empirical universality and non-universality of local dynamics in the Sherrington-Kirkpatrick model
di: Liu, Grace, et al.
Pubblicazione: (2025)

Emergence of social hierarchies in a society with two competitive groups
di: Sadurní, Marc, et al.
Pubblicazione: (2024)

New Berry-Esseen bounds for parameter estimation of Gaussian processes observed at high frequency
di: Es-Sebaiy, Khalifa, et al.
Pubblicazione: (2026)

A Pair of Bayesian Network Structures has Undecidable Conditional Independencies
di: Li, Cheuk Ting
Pubblicazione: (2024)

Communication with Imperfectly Shared Randomness
di: Canonne, Clément L., et al.
Pubblicazione: (2014)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
di: Buhai, Rares-Darius, et al.
Pubblicazione: (2024)