Broadcasting on trees and the Ising model.

DOI10.1214/aoap/1019487349zbMath1052.60076OpenAlexW1996199671WikidataQ105965927 ScholiaQ105965927MaRDI QIDQ1884823

Leonard J. Schulman, Yuval Peres, William S. Evans, Claire M. Kenyon

Publication date: 27 October 2004

Published in: The Annals of Applied Probability (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1214/aoap/1019487349

zbMATH Keywords

Ising model spin electrical network noisy computation Percolation

Mathematics Subject Classification ID

Network design and communication in computer systems (68M10) Interacting random processes; statistical mechanics type models; percolation theory (60K35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Discrete mathematics in relation to computer science (68R99)

Related Items

Reconstruction on trees: Beating the second eigenvalue, The Ising model on diluted graphs and strong amenability, An impossibility result for reconstruction in the degree-corrected stochastic block model, Continuous symmetry breaking along the Nishimori line, Reconstructibility of a general DNA evolution model, Cutoff for the noisy voter model, Robust reconstruction on trees is determined by the second eigenvalue., On memory in exponentially expanding spaces, Weighted Message Passing and Minimum Energy Flow for Heterogeneous Stochastic Block Models with Side Information, Reconstruction of random colourings, Concentration of Markov chains indexed by trees, On the variational distance of two trees, Necessary and sufficient conditions for consistent root reconstruction in Markov models on trees, An information-percolation bound for spin synchronization on general graphs, Identifiability and inference of non-parametric rates-across-sites models on large-scale phylo\-genies, Application of the information-percolation method to reconstruction problems on graphs, Stability of the phase transition of critical-field Ising model on Cayley trees under inhomogeneous external fields, Analyzing the fitch method for reconstructing ancestral states on ultrametric phylogenetic trees, Geometric ergodicity and the spectral gap of non-reversible Markov chains, Non-linear log-Sobolev inequalities for the Potts semigroup and applications to reconstruction problems, Community detection in the sparse hypergraph stochastic block model, Broadcasting‐induced colorings of preferential attachment trees, Continuity of the Ising phase transition on nonamenable groups, Combinatorial statistics and the sciences, Glassy states: the free Ising model on a tree, Spectral measures of factor of i.i.d. processes on vertex-transitive graphs, Asymptotic mutual information for the balanced binary stochastic block model, Factors of IID on Trees, Factor models on locally tree-like graphs, On the inference of large phylogenies with long branches: how long is too long?, Information flow on trees, The mathematics and statistics of voting power, A phase transition for a random cluster model on phylogenetic trees., Ising critical exponents on random trees and graphs, Efficient estimation of the accuracy of the maximum likelihood method for ancestral state reconstruction, Reconstruction and estimation in the planted partition model, Phase transition on the convergence rate of parameter estimation under an Ornstein-Uhlenbeck diffusion on a tree, The tightness of the Kesten-Stigum reconstruction bound of symmetric model with multiple mutations, Phase transition in the sample complexity of likelihood-based phylogeny inference, Community Detection and Stochastic Block Models, Mixing time of a kinetically constrained spin model on trees: power law scaling at criticality, A manifold of pure Gibbs states of the Ising model on the Lobachevsky plane, Ising models on locally tree-like graphs, Glauber dynamics on trees: Boundary conditions and mixing time, Teasing Apart Two Trees, Inferring ancestral sequences in taxon-rich phylogenies, The critical Ising model on trees, concave recursions and nonlinear capacity, Meet and merge: approximation algorithms for confluent flows, Mixing time of critical Ising model on trees is polynomial in the height, Global alignment of molecular sequences via ancestral state reconstruction, Gibbs measures and phase transitions on sparse random graphs, Reconstruction for the Potts model, Glauber dynamics on trees and hyperbolic graphs, Evolutionary trees and the Ising model on the Bethe lattice: A proof of Steel's conjecture, Phase ordering after a deep quench: the stochastic Ising and hard core gas models on a tree, Information reconstruction on an infinite tree for a \(4\times 4\)-state asymmetric model with community effects, The impact and interplay of long and short branches on phylogenetic information content, Gibbs field approach for evolutionary analysis of regulatory signal of gene expression, Scaling and universality in continuous length combinatorial optimization, Majority rule has transition ratio 4 on Yule trees under a 2-state symmetric model, Statistically consistent and computationally efficient inference of ancestral DNA sequences in the TKF91 model under dense taxon sampling, Robust phase transitions for Heisenberg and other models on general trees, Phase transitions in phylogeny, Sufficient condition for root reconstruction by parsimony on binary trees with general weights, Finding Rumor Sources on Random Trees, On the computational tractability of statistical estimation on amenable graphs, Large degree asymptotics and the reconstruction threshold of the asymmetric binary channels, Graph homomorphisms and phase transitions, Ising model on trees and factors of IID, Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models, Phase Transition of the Reconstructability of a General Model with Different In-Community and Out-Community Mutations on an Infinite Tree, An impossibility result for phylogeny reconstruction from \(k\)-mer counts, Broadcasting on random recursive trees

Cites Work