Finite-depth posterior law and Bayes accuracy in the critical window of a planted 3-SAT tree

How accurately can one infer the root spin of a planted 3-SAT tree from the literal signs through depth h and the exact spins at that depth? We let every variable have a Poisson number of child clauses with mean dₕ = d∗(1 + s/h), where d∗ is the Kesten–Stigum degree. If exact-leaf reconstruction fails at d∗ and the quadratic coefficient c of the posterior second-moment recursion there is negative, then h times the posterior second moment converges to A(s) = s/(|c|(1 − exp(−s))), with A(0) = 1/|c|. The root posterior mean multiplied by √h converges to √(A(s)W) G, where G is standard normal and W is the independent Galton–Watson martingale limit of the tree at degree d∗. The convergence holds jointly with each fixed initial portion of the tree, uniformly for s in compact sets. Thus √h times the optimal accuracy advantage over random guessing converges to √(A(s)/(2π)) E[√W]. We also obtain the limiting fourth moment and a Gaussian approximation conditional on the full unmarked tree. The conditional variance is estimated by the normalized population at generation L, taking h to infinity before L. The proof sums a reciprocal moment recursion and compares the posterior on a fixed initial block to a weighted sum of independent boundary messages. The hypotheses hold for the clause-distribution-control plantings with all-true pattern probability 0 ≤ p₀ ≤ 0.0321.

Authors

Publication Details

Journal
Zenodo (CERN European Organization for Nuclear Research)
Published
2026-11-18
DOI
https://doi.org/10.5281/zenodo.24359018
Primary Topic
Constraint Satisfaction and Optimization
Type
preprint
Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
NOV
preprint

Finite-depth posterior law and Bayes accuracy in the critical window of a planted 3-SAT tree

Yan Ru Pei
Zenodo (CERN European Organization for Nuclear Research)
Constraint Satisfaction and Optimization
preprint

Finite-depth posterior law and Bayes accuracy in the critical window of a planted 3-SAT tree

Yan Ru Pei
preprint en

Abstract

How accurately can one infer the root spin of a planted 3-SAT tree from the literal signs through depth h and the exact spins at that depth? We let every variable have a Poisson number of child clauses with mean dₕ = d∗(1 + s/h), where d∗ is the Kesten–Stigum degree. If exact-leaf reconstruction fails at d∗ and the quadratic coefficient c of the posterior second-moment recursion there is negative, then h times the posterior second moment converges to A(s) = s/(|c|(1 − exp(−s))), with A(0) = 1/|c|. The root posterior mean multiplied by √h converges to √(A(s)W) G, where G is standard normal and W is the independent Galton–Watson martingale limit of the tree at degree d∗. The convergence holds jointly with each fixed initial portion of the tree, uniformly for s in compact sets. Thus √h times the optimal accuracy advantage over random guessing converges to √(A(s)/(2π)) E[√W]. We also obtain the limiting fourth moment and a Gaussian approximation conditional on the full unmarked tree. The conditional variance is estimated by the normalized population at generation L, taking h to infinity before L. The proof sums a reciprocal moment recursion and compares the posterior on a fixed initial block to a weighted sum of independent boundary messages. The hypotheses hold for the clause-distribution-control plantings with all-true pattern probability 0 ≤ p₀ ≤ 0.0321.

Zenodo (CERN European Organization for Nuclear Research)
Constraint Satisfaction and Optimization
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.

Laika access coming soon