On the computational tractability of statistical estimation on amenable graphs
DOI10.1007/s00440-021-01092-yzbMath1491.62043arXiv1904.03313OpenAlexW3211943077MaRDI QIDQ2067660
Publication date: 18 January 2022
Published in: Probability Theory and Related Fields (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1904.03313
Factor analysis and principal components; correspondence analysis (62H25) Random graphs (graph-theoretic aspects) (05C80) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Disordered systems (random Ising models, random Schrödinger operators, etc.) in equilibrium statistical mechanics (82B44) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40) Probabilistic graphical models (62H22)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Reconstruction for the Potts model
- High-dimensional analysis of semidefinite relaxations for sparse principal components
- Reconstruction on trees and spin glass transition
- Finding hidden cliques of size \(\sqrt{N/e}\) in nearly linear time
- A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
- Information flow on trees
- Information-theoretic thresholds from the cavity method
- A proof of the block model threshold conjecture
- Fundamental limits of symmetric low-rank matrix estimation
- On the concentration of eigenvalues of random symmetric matrices
- Recurrence of distributional limits of finite planar graphs
- Broadcasting on trees and the Ising model.
- Robust reconstruction on trees is determined by the second eigenvalue.
- Application of the information-percolation method to reconstruction problems on graphs
- Group synchronization on grids
- Factor models on locally tree-like graphs
- Processes on unimodular random networks
- An information-percolation bound for spin synchronization on general graphs
- Probability on Trees and Networks
- Information, Physics, and Computation
- Large Cliques Elude the Metropolis Process
- Random Geometric Graphs
- Community Detection and Stochastic Block Models
- Proof of the Achievability Conjectures for the General Stochastic Block Model
- Asymptotic mutual information for the balanced binary stochastic block model
- A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
- Finding and certifying a large hidden clique in a semirandom graph
- How well do local algorithms solve semidefinite programs?
- The Lov\'asz Theta Function for Random Regular Graphs and Community Detection in the Hard Regime
- Optimal errors and phase transitions in high-dimensional generalized linear models
- Rejoinder
- Community detection thresholds and the weak Ramanujan property
- Fast spectral algorithms from sum-of-squares proofs: tensor decomposition and planted sparse vectors
- Information Theory and Statistics: A Tutorial
- The two possible values of the chromatic number of a random graph
This page was built for publication: On the computational tractability of statistical estimation on amenable graphs
