Cover Image

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Lou, Mengqi, Bresler, Guy, Pananjady, Ashwin
Format:	Preprint
Published:	2025
Subjects:	Statistics Theory Computational Complexity Information Theory Machine Learning
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

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

Just Wing It: Near-Optimal Estimation of Missing Mass in a Markovian Sequence
by: Pananjady, Ashwin, et al.
Published: (2024)

Estimating stationary mass, frequency by frequency
by: Nakul, Milind, et al.
Published: (2025)

Alternating minimization for generalized rank one matrix sensing: Sharp predictions from a random initialization
by: Chandrasekher, Kabir Aladin, et al.
Published: (2022)

Hyperparameter tuning via trajectory predictions: Stochastic prox-linear methods in matrix sensing
by: Lou, Mengqi, et al.
Published: (2024)

Efficient Pauli channel estimation with logarithmic quantum memory
by: Chen, Sitan, et al.
Published: (2023)

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

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

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

Predictive inference for time series: why is split conformal effective despite temporal dependence?
by: Barber, Rina Foygel, et al.
Published: (2025)

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

Lower Bounds for Learning Quantum States with Single-Copy Measurements
by: Lowe, Angus, et al.
Published: (2022)

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

Learning to erase quantum states: thermodynamic implications of quantum learning theory
by: Zhao, Haimeng, et al.
Published: (2025)

Approximate Computation via Le Cam Simulability
by: Akdemir, Deniz
Published: (2025)

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

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

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

Improved Hardness Results for Learning Intersections of Halfspaces
by: Tiegel, Stefan
Published: (2024)

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

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

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

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

Learning from Equivalence Queries, Revisited
by: Braverman, Mark, et al.
Published: (2026)

Leave a Window Out: Modifying the Jackknife for Predictive Inference in Time Series
by: Jiang, Hanyang, et al.
Published: (2026)

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

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

Polynomial-Time Optimal Group Selection via the Double-Commutator Eigenvalue Problem
by: Thornton, Mitchell A.
Published: (2026)

Optimal Sequential Recommendations: Exploiting User and Item Structure
by: Karzand, Mina, et al.
Published: (2025)

Thresholds for Reconstruction of Random Hypergraphs From Graph Projections
by: Bresler, Guy, et al.
Published: (2025)

Near-Optimal Learning and Planning in Separated Latent MDPs
by: Chen, Fan, et al.
Published: (2024)

Cryptographic Hardness of Score Estimation
by: Song, Min Jae
Published: (2024)

Efficient Algorithm for Sparse Fourier Transform of Generalized $q$-ary Functions
by: Tsui, Darin, et al.
Published: (2025)

Optimal lower bounds for Quantum Learning via Information Theory
by: Hadiashar, Shima Bab, et al.
Published: (2023)

State evolution beyond first-order methods I: Rigorous predictions and finite-sample guarantees
by: Celentano, Michael, et al.
Published: (2025)

The Optimal Approximation Factor in Density Estimation
by: Bousquet, Olivier, et al.
Published: (2019)

Partial and Exact Recovery of a Random Hypergraph from its Graph Projection
by: Bresler, Guy, et al.
Published: (2025)

On the best approximation by finite Gaussian mixtures
by: Ma, Yun, et al.
Published: (2024)

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