Image de couverture de livre

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Tang, Runshi, Han, Yuefeng, Zhang, Anru R.
Format:	Preprint
Publié:	2026
Sujets:	Statistics Theory Computational Complexity
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Detection Is Harder Than Estimation in Certain Regimes: Inference for Moment and Cumulant Tensors
par: Tang, Runshi, et autres
Publié: (2026)

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
par: Chen, Siyu, et autres
Publié: (2025)

Approximate Computation via Le Cam Simulability
par: Akdemir, Deniz
Publié: (2025)

Sharp Thresholds Imply Circuit Lower Bounds: from random 2-SAT to Planted Clique
par: Gamarnik, David, et autres
Publié: (2023)

Stable Algorithms Lower Bounds for Estimation
par: Yu, Xifan, et autres
Publié: (2026)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
par: Luo, Yuetian, et autres
Publié: (2023)

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
par: Bresler, Guy, et autres
Publié: (2025)

Mode-wise Principal Subspace Pursuit and Matrix Spiked Covariance Model
par: Tang, Runshi, et autres
Publié: (2023)

Computational lower bounds for multi-frequency group synchronization
par: Kireeva, Anastasia, et autres
Publié: (2024)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
par: Buhai, Rares-Darius, et autres
Publié: (2024)

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

Revisit CP Tensor Decomposition: Statistical Optimality and Fast Convergence
par: Tang, Runshi, et autres
Publié: (2025)

Lower Bounds for Approximate Sign Rank
par: Bindua, Riju, et autres
Publié: (2026)

Exponential Lower Bounds for 2-query Relaxed Locally Decodable Codes
par: Block, Alexander R., et autres
Publié: (2026)

The monotonicity of the Franz-Parisi potential is equivalent with Low-degree MMSE lower bounds
par: Tsirkas, Konstantinos, et autres
Publié: (2026)

Random Circuit Sampling: Fourier Expansion and Statistics
par: Kalai, Gil, et autres
Publié: (2024)

Causal Discovery under Latent Class Confounding
par: Mazaheri, Bijan, et autres
Publié: (2023)

Learning High-dimensional Gaussians from Censored Data
par: Bhattacharyya, Arnab, et autres
Publié: (2025)

Improved Hardness Results for Learning Intersections of Halfspaces
par: Tiegel, Stefan
Publié: (2024)

On the Hardness of Learning One Hidden Layer Neural Networks
par: Li, Shuchen, et autres
Publié: (2024)

On Computationally Efficient Multi-Class Calibration
par: Gopalan, Parikshit, et autres
Publié: (2024)

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
par: Yu, Xifan, et autres
Publié: (2024)

Low degree conjecture implies sharp computational thresholds in stochastic block model
par: Ding, Jingqiu, et autres
Publié: (2025)

Exponential Lower Bounds for Locally Decodable and Correctable Codes for Insertions and Deletions
par: Blocki, Jeremiah, et autres
Publié: (2021)

Tarski Lower Bounds from Multi-Dimensional Herringbones
par: Brânzei, Simina, et autres
Publié: (2025)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
par: Kelner, Jonathan, et autres
Publié: (2024)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
par: Lou, Mengqi, et autres
Publié: (2025)

A Unifying Integral Representation of the Gamma Function and Its Reciprocal
par: Hansen, Peter Reinhard, et autres
Publié: (2025)

Landauer Principle and Thermodynamics of Computation
par: Chattopadhyay, Pritam, et autres
Publié: (2025)

Information-Theoretic Bounds and Task-Centric Learning Complexity for Real-World Dynamic Nonlinear Systems
par: Bulusu, Sri Satish Krishna Chaitanya, et autres
Publié: (2025)

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
par: R., Abhishek Hegade K., et autres
Publié: (2025)

Average-Case Reductions for $k$-XOR and Tensor PCA
par: Bresler, Guy, et autres
Publié: (2026)

Symmetric Perceptrons, Number Partitioning and Lattices
par: Vafa, Neekon, et autres
Publié: (2025)

Model-agnostic super-resolution in high dimensions
par: Chen, Xi, et autres
Publié: (2025)

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
par: Janzer, Oliver, et autres
Publié: (2024)

Classically Sampling Noisy Quantum Circuits in Quasi-Polynomial Time under Approximate Markovianity
par: Zhang, Yifan F., et autres
Publié: (2025)

Tight Lower Bound for Approximating Parametrized Maximum Likelihood Decoding under ETH
par: Gupta, Rishav, et autres
Publié: (2026)

Information-Theoretic Lower Bounds for Approximating Monomials via Optimal Quantum Tsallis Entropy Estimation
par: Wang, Qisheng
Publié: (2025)

A Quadratic Lower Bound for Stable Roommates Solvability
par: Rosenbaum, Will
Publié: (2025)

Towards Exponential Quantum Improvements in Solving Cardinality-Constrained Binary Optimization
par: Yuan, Haomu, et autres
Publié: (2026)