Buchumschlag

Low degree conjecture implies sharp computational thresholds in stochastic block model

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ding, Jingqiu, Hua, Yiding, Slot, Lucas, Steurer, David
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Computational Complexity Machine Learning Statistics Theory Computation
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Rate-optimal community detection near the KS threshold via node-robust algorithms
von: Ding, Jingqiu, et al.
Veröffentlicht: (2025)

Computational-Statistical Gaps for Improper Learning in Sparse Linear Regression
von: Buhai, Rares-Darius, et al.
Veröffentlicht: (2024)

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

Private graphon estimation via sum-of-squares
von: Chen, Hongjie, et al.
Veröffentlicht: (2024)

Computational Lower Bounds for Graphon Estimation via Low-degree Polynomials
von: Luo, Yuetian, et al.
Veröffentlicht: (2023)

Computational Complexity of Statistics: New Insights from Low-Degree Polynomials
von: Wein, Alexander S.
Veröffentlicht: (2025)

Efficient reductions from a Gaussian source with applications to statistical-computational tradeoffs
von: Lou, Mengqi, et al.
Veröffentlicht: (2025)

Low-degree estimation thresholds in planted hypergraphs and tensor PCA
von: Fu, Daniel, et al.
Veröffentlicht: (2026)

Learning High-dimensional Gaussians from Censored Data
von: Bhattacharyya, Arnab, et al.
Veröffentlicht: (2025)

Causal Discovery under Latent Class Confounding
von: Mazaheri, Bijan, et al.
Veröffentlicht: (2023)

Improved Hardness Results for Learning Intersections of Halfspaces
von: Tiegel, Stefan
Veröffentlicht: (2024)

On the Hardness of Learning One Hidden Layer Neural Networks
von: Li, Shuchen, et al.
Veröffentlicht: (2024)

An Optimized Franz-Parisi Criterion and its Equivalence with SQ Lower Bounds
von: Chen, Siyu, et al.
Veröffentlicht: (2025)

The stochastic block model has the overlap graph property for modularity
von: Bhamidi, Shankar, et al.
Veröffentlicht: (2026)

Detection of local geometry in random graphs: information-theoretic and computational limits
von: Bok, Jinho, et al.
Veröffentlicht: (2026)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
von: Chen, Sitan, et al.
Veröffentlicht: (2026)

Near-Optimal Learning and Planning in Separated Latent MDPs
von: Chen, Fan, et al.
Veröffentlicht: (2024)

Cryptographic Hardness of Score Estimation
von: Song, Min Jae
Veröffentlicht: (2024)

Efficient Pauli channel estimation with logarithmic quantum memory
von: Chen, Sitan, et al.
Veröffentlicht: (2023)

Derandomizing Multi-Distribution Learning
von: Larsen, Kasper Green, et al.
Veröffentlicht: (2024)

On Computationally Efficient Multi-Class Calibration
von: Gopalan, Parikshit, et al.
Veröffentlicht: (2024)

Lasso with Latents: Efficient Estimation, Covariate Rescaling, and Computational-Statistical Gaps
von: Kelner, Jonathan, et al.
Veröffentlicht: (2024)

Information-Theoretic Bounds and Task-Centric Learning Complexity for Real-World Dynamic Nonlinear Systems
von: Bulusu, Sri Satish Krishna Chaitanya, et al.
Veröffentlicht: (2025)

Learning to erase quantum states: thermodynamic implications of quantum learning theory
von: Zhao, Haimeng, et al.
Veröffentlicht: (2025)

Tensor cumulants for statistical inference on invariant distributions
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

A sharp interaction-degree threshold for simulating QAOA
von: Āboliņš, Ralfs, et al.
Veröffentlicht: (2026)

Low-degree learning and the metric entropy of polynomials
von: Eskenazis, Alexandros, et al.
Veröffentlicht: (2022)

Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust
von: Chen, Hongjie, et al.
Veröffentlicht: (2024)

Uncertainty quantification by block bootstrap for differentially private stochastic gradient descent
von: Dette, Holger, et al.
Veröffentlicht: (2024)

Is stochastic thermodynamics the key to understanding the energy costs of computation?
von: Wolpert, David, et al.
Veröffentlicht: (2023)

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning
von: Chakrabarty, Deeparnab, et al.
Veröffentlicht: (2025)

Stochastic thermodynamics of computation
von: Wolpert, David H.
Veröffentlicht: (2019)

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

Computational Equivalence of Spiked Covariance and Spiked Wigner Models via Gram-Schmidt Perturbation
von: Bresler, Guy, et al.
Veröffentlicht: (2025)

A Framework for Computational Lower Bounds in Nontrivial Norm Approximation
von: Tang, Runshi, et al.
Veröffentlicht: (2026)

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

Low coordinate degree algorithms II: Categorical signals and generalized stochastic block models
von: Kunisky, Dmitriy
Veröffentlicht: (2024)

Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing
von: Kunisky, Dmitriy
Veröffentlicht: (2024)

Approximate Computation via Le Cam Simulability
von: Akdemir, Deniz
Veröffentlicht: (2025)

Mixture of multilayer stochastic block models for multiview clustering
von: De Santiago, Kylliann, et al.
Veröffentlicht: (2024)