Buchumschlag

Sharp Phase Transitions in Estimation with Low-Degree Polynomials

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Sohn, Youngtak, Wein, Alexander S.
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Statistics Theory Computational Complexity Data Structures and Algorithms Probability
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

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

Strong Low Degree Hardness for the Number Partitioning Problem
von: Mallarapu, Rushil, et al.
Veröffentlicht: (2025)

Statistical inference of a ranked community in a directed graph
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

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

Large Average Subtensor Problem: Ground-State, Algorithms, and Algorithmic Barriers
von: R., Abhishek Hegade K., et al.
Veröffentlicht: (2025)

Testing Convex Truncation
von: De, Anindya, et al.
Veröffentlicht: (2023)

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

Inference of rankings planted in random tournaments
von: Kunisky, Dmitriy, et al.
Veröffentlicht: (2024)

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

Counting Stars is Constant-Degree Optimal For Detecting Any Planted Subgraph
von: Yu, Xifan, et al.
Veröffentlicht: (2024)

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

Stable Algorithms Lower Bounds for Estimation
von: Yu, Xifan, et al.
Veröffentlicht: (2026)

The Quasi-Polynomial Low-Degree Conjecture is False
von: Buhai, Rares-Darius, et al.
Veröffentlicht: (2025)

Polynomial-time sampling despite disorder chaos
von: Ma, Eric, et al.
Veröffentlicht: (2025)

Random Matrices, Intrinsic Freeness, and Sharp Non-Asymptotic Inequalities
von: Bandeira, Afonso S.
Veröffentlicht: (2025)

Model-agnostic super-resolution in high dimensions
von: Chen, Xi, et al.
Veröffentlicht: (2025)

The Low-Degree Hardness of Finding Large Independent Sets in Sparse Random Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2024)

Fast mixing in Ising models with a negative spectral outlier via Gaussian approximation
von: Mikulincer, Dan, et al.
Veröffentlicht: (2025)

Sharp Thresholds for the Overlap Gap Property: Ising $p$-Spin Glass and Random $k$-SAT
von: Kızıldağ, Eren C.
Veröffentlicht: (2023)

Algorithmic Phase Transition for Large Independent Sets in Dense Hypergraphs
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2026)

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

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
von: Moka, Sarat, et al.
Veröffentlicht: (2026)

Hardness of sampling for the anti-ferromagnetic Ising model on random graphs
von: Huang, Neng, et al.
Veröffentlicht: (2024)

Random tensor isomorphism under orthogonal and unitary actions
von: Chizewer, Jeremy, et al.
Veröffentlicht: (2026)

On the average-case complexity landscape for Tensor-Isomorphism-complete problems over finite fields
von: Li, Tiange, et al.
Veröffentlicht: (2026)

Explicit Orthogonal Arrays and Universal Hashing with Arbitrary Parameters
von: Harvey, Nicholas, et al.
Veröffentlicht: (2024)

Detecting Low-Degree Truncation
von: De, Anindya, et al.
Veröffentlicht: (2024)

Sharp Online Hardness for Large Balanced Independent Sets
von: Dhawan, Abhishek, et al.
Veröffentlicht: (2025)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

On the Low-Temperature MCMC threshold: the cases of sparse tensor PCA, sparse regression, and a geometric rule
von: Chen, Zongchen, et al.
Veröffentlicht: (2024)

Low-degree phase transitions for detecting a planted clique in sublinear time
von: Mardia, Jay, et al.
Veröffentlicht: (2024)

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

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)

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

Some easy optimization problems have the overlap-gap property
von: Li, Shuangping, et al.
Veröffentlicht: (2024)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
von: Mao, Songtao
Veröffentlicht: (2026)

Geometric Interpretation of 3-SAT and Phase Transition
von: Gillet, Frederic
Veröffentlicht: (2025)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
von: Rai, Shanthanu S
Veröffentlicht: (2024)

Achievability of Heterogeneous Hypergraph Recovery from its Graph Projection
von: Morgan, Alexander, et al.
Veröffentlicht: (2026)