Optimal Low degree hardness for Broadcasting on Trees
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914158756233216 |
|---|---|
| author | Huang, Han Mossel, Elchanan |
| author_facet | Huang, Han Mossel, Elchanan |
| contents | Broadcasting on trees is a fundamental model from statistical physics that plays an important role in information theory, noisy computation and phylogenetic reconstruction within computational biology and linguistics. While this model permits efficient linear-time algorithms for the inference of the root from the leaves, recent work suggests that non-trivial computational complexity may be required for inference.
The inference of the root state can be performed using the celebrated Belief Propagation (BP) algorithm, which achieves Bayes-optimal performance. Although BP runs in linear time using real arithmetic operations, recent research indicates that it requires non-trivial computational complexity using more refined complexity measures.
Moitra, Mossel, and Sandon demonstrated such complexity by constructing a Markov chain for which estimating the root better than random guessing (for typical inputs) is $NC^1$-complete. Kohler and Mossel constructed chains where, for trees with $N$ leaves, achieving better-than-random root recovery requires polynomials of degree $N^{Ω(1)}$. The papers above raised the question of whether such complexity bounds hold generally below the celebrated Kesten-Stigum bound.
In a recent work, Huang and Mossel established a general degree lower bound of $Ω(\log N)$ below the Kesten-Stigum bound. Specifically, they proved that any function expressed as a linear combination of functions of at most $O(log N)$ leaves has vanishing correlation with the root. In this work, we get an exponential improvement of this lower bound by establishing an $N^{Ω(1)}$ degree lower bound, for any broadcast process in the whole regime below the Kesten-Stigum bound. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_04861 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Optimal Low degree hardness for Broadcasting on Trees Huang, Han Mossel, Elchanan Probability Broadcasting on trees is a fundamental model from statistical physics that plays an important role in information theory, noisy computation and phylogenetic reconstruction within computational biology and linguistics. While this model permits efficient linear-time algorithms for the inference of the root from the leaves, recent work suggests that non-trivial computational complexity may be required for inference. The inference of the root state can be performed using the celebrated Belief Propagation (BP) algorithm, which achieves Bayes-optimal performance. Although BP runs in linear time using real arithmetic operations, recent research indicates that it requires non-trivial computational complexity using more refined complexity measures. Moitra, Mossel, and Sandon demonstrated such complexity by constructing a Markov chain for which estimating the root better than random guessing (for typical inputs) is $NC^1$-complete. Kohler and Mossel constructed chains where, for trees with $N$ leaves, achieving better-than-random root recovery requires polynomials of degree $N^{Ω(1)}$. The papers above raised the question of whether such complexity bounds hold generally below the celebrated Kesten-Stigum bound. In a recent work, Huang and Mossel established a general degree lower bound of $Ω(\log N)$ below the Kesten-Stigum bound. Specifically, they proved that any function expressed as a linear combination of functions of at most $O(log N)$ leaves has vanishing correlation with the root. In this work, we get an exponential improvement of this lower bound by establishing an $N^{Ω(1)}$ degree lower bound, for any broadcast process in the whole regime below the Kesten-Stigum bound. |
| title | Optimal Low degree hardness for Broadcasting on Trees |
| topic | Probability |
| url | https://arxiv.org/abs/2502.04861 |