Copertina

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Bresler, Guy, Harbuzova, Alina
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Statistics Theory Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
di: Lou, Mengqi, et al.
Pubblicazione: (2025)

Near-Optimal Time-Sparsity Trade-Offs for Solving Noisy Linear Equations
di: Bangachev, Kiril, et al.
Pubblicazione: (2024)

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

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
di: Chen, Siyu, et al.
Pubblicazione: (2025)

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

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
di: Kelner, Jonathan, et al.
Pubblicazione: (2024)

Computational lower bounds for multi-frequency group synchronization
di: Kireeva, Anastasia, et al.
Pubblicazione: (2024)

On Computationally Efficient Multi-Class Calibration
di: Gopalan, Parikshit, et al.
Pubblicazione: (2024)

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

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
di: Wein, Alexander S.
Pubblicazione: (2025)

Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors
di: Tang, Runshi, et al.
Pubblicazione: (2026)

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

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
di: Luo, Yuetian, et al.
Pubblicazione: (2023)

Inference for Spiked Eigenstructure under Generalized Covariance and Correlation Models
di: Yin, Yanqing, et al.
Pubblicazione: (2024)

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

Model-agnostic super-resolution in high dimensions
di: Chen, Xi, et al.
Pubblicazione: (2025)

Learning High-dimensional Gaussians from Censored Data
di: Bhattacharyya, Arnab, et al.
Pubblicazione: (2025)

Graph Quasirandomness for Hypothesis Testing of Stochastic Block Models
di: Bangachev, Kiril, et al.
Pubblicazione: (2025)

Random Circuit Sampling: Fourier Expansion and Statistics
di: Kalai, Gil, et al.
Pubblicazione: (2024)

Causal Discovery under Latent Class Confounding
di: Mazaheri, Bijan, et al.
Pubblicazione: (2023)

Improved Hardness Results for Learning Intersections of Halfspaces
di: Tiegel, Stefan
Pubblicazione: (2024)

On the Hardness of Learning One Hidden Layer Neural Networks
di: Li, Shuchen, et al.
Pubblicazione: (2024)

Low degree conjecture implies sharp computational thresholds in stochastic block model
di: Ding, Jingqiu, et al.
Pubblicazione: (2025)

The Asymptotic Properties of the Extreme Eigenvectors of High-dimensional Generalized Spiked Covariance Model
di: Pu, Zhangni, et al.
Pubblicazione: (2024)

Spectrally-Corrected and Regularized QDA Classifier for Spiked Covariance Model
di: Luo, Wenya, et al.
Pubblicazione: (2025)

Landauer Principle and Thermodynamics of Computation
di: Chattopadhyay, Pritam, et al.
Pubblicazione: (2025)

Computationally efficient reductions between some statistical models
di: Lou, Mengqi, et al.
Pubblicazione: (2024)

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

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
di: Yu, Xifan, et al.
Pubblicazione: (2024)

Stable Algorithms Lower Bounds for Estimation
di: Yu, Xifan, et al.
Pubblicazione: (2026)

Generalization for Least Squares Regression With Simple Spiked Covariances
di: Li, Jiping, et al.
Pubblicazione: (2024)

A Unifying Integral Representation of the Gamma Function and Its Reciprocal
di: Hansen, Peter Reinhard, et al.
Pubblicazione: (2025)

On the Equivalence of Gaussian Graphical Models Defined on Complete Bipartite Graphs
di: Molkaraie, Mehdi
Pubblicazione: (2025)

On The Fourier Coefficients of High-Dimensional Random Geometric Graphs
di: Bangachev, Kiril, et al.
Pubblicazione: (2024)

Optimal Differentially Private PCA and Estimation for Spiked Covariance Matrices
di: Cai, T. Tony, et al.
Pubblicazione: (2024)

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

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)

Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization
di: Yuan, Haomu, et al.
Pubblicazione: (2026)