← 研踪 PaperTrailarXiv:1601.04794 · v4
Concentration Inequalities for Branching Random Walks with Applications to Phase Transitions in CSPs
首次提交 2016-01-19 12:10
版本更新 2026-11-06 00:35
雷达观测 2026-11-09 10:16
摘要
A new framework is developed for studying phase transitions in random CSPs, from which a range of new results follows. Motivated by phase transition problems in CSPs, a more general concentration inequality is proved that retains classical sub-Gaussian tails under a mild global linear-growth condition $|S_n| < Cn$, relaxing the bounded-increment assumption to finite exponential moments and requiring neither independence nor the martingale property. We further extend the concentration inequality to branching random walks (BRW), obtaining the first concentration inequality for BRW. As applications, we derive partial differential equations (PDEs) for the $K$-SAT and $q$-COL backbones, yielding new results, including \textbf{(a)} a resolution of the long-standing open question of where $(2+p)$-SAT transition changes from second to first order; \textbf{(b)} rigorous results for $α_d$ in $K$-SAT, which give new lower bounds on the phase transition for 3-SAT (4.0029 vs. 3.51) and 4-SAT (8.360 vs. 7.91); and \textbf{(c)} the prefactor of the 2-SAT critical window.
作者备注：57 pages, 15 figures
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v4 · 2026-11-06 00:35 · 最新观测版本
Concentration Inequalities for Branching Random Walks with Applications to Phase Transitions in CSPs
A new framework is developed for studying phase transitions in random CSPs, from which a range of new results follows. Motivated by phase transition problems in CSPs, a more general concentration inequality is proved that retains classical sub-Gaussian tails under a mild global linear-growth condition $|S_n| < Cn$, relaxing the bounded-increment assumption to finite exponential moments and requiring neither independence nor the martingale property. We further extend the concentration inequality to branching random walks (BRW), obtaining the first concentration inequality for BRW. As applications, we derive partial differential equations (PDEs) for the $K$-SAT and $q$-COL backbones, yielding new results, including \textbf{(a)} a resolution of the long-standing open question of where $(2+p)$-SAT transition changes from second to first order; \textbf{(b)} rigorous results for $α_d$ in $K$-SAT, which give new lower bounds on the phase transition for 3-SAT (4.0029 vs. 3.51) and 4-SAT (8.360 vs. 7.91); and \textbf{(c)} the prefactor of the 2-SAT critical window.
查看此版本解读 →查看此版本原文 ↗