Consensus time for asynchronous ℓp relaxation: graph dependence
Abstract
We study the asynchronous ℓp relaxation introduced by Amir, Nazarov, and Peres: at each step, a uniformly chosen vertex minimizes its incident ℓp energy. For the profile ft after t updates, let Tp(G,1/2):= suplVert f0rVert∞≤1 𝔼[min{t≥0:osc(ft)≤1/2}]. For 1<p<∞, we obtain graph-dependent estimates for boxes, trees, and conductance expanders. On the nearest-neighbor box [L]d, for d,L≥2 and n=Ld, the answer is, up to logarithmic factors, nd1/(p−1)Lp/(p−1) for 1<p<2 and ndL2 for p≥2. On bounded-degree trees, an explicit rerooting-invariant parameter TG determines the answer up to logarithmic factors; for arbitrary trees it gives upper and lower bounds that differ additionally by the maximum degree. If the volume conductance h(G)≥ h0>0, then Tp(G,1/2)=Θp,h0(nlog n) without a degree assumption. At p=∞, every connected graph satisfies T∞(G,1/2)≥ c nD2/Δ, where D and Δ are its diameter and maximum degree.
Related
- L2-error bounds for covariation estimation under asynchronous mixed time-space sampling
- Input-to-Output Stability and Consensus Control of Opinion Dynamics on Graph State-Space
- DistFlow and Its Conic Relaxation: Regularity, Monotonicity, and Hybrid Exactness via Graph Decomposition
- Hitting-Time Bounds for Asynchronous Q-Learning
- On Large Drift Enhancement for the Relaxation Time of Averages
BibTeX
@misc{gan2026consensus,
title = {{Consensus time for asynchronous $\ell^p$ relaxation: graph dependence}},
author = {Chenyu Gan},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.03856},
eprint = {2609.03856},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.03856},
}
RIS
TY - UNPB
TI - Consensus time for asynchronous ℓ^p relaxation: graph dependence
AU - Chenyu Gan
PY - 2026
DA - 2026/09/03
PB - arXiv
DO - 10.48550/arxiv.2609.03856
UR - https://arxiv.org/abs/2609.03856
AB - We study the asynchronous ℓ^p relaxation introduced by Amir, Nazarov, and Peres: at each step, a uniformly chosen vertex minimizes its incident ℓ^p energy. For the profile f_t after t updates, let T_p(G,1/2):= sup_lVert f_0rVert_∞≤1 𝔼[min{t≥0:osc(f_t)≤1/2}]. For 1<p<∞, we obtain graph-dependent estimates for boxes, trees, and conductance expanders. On the nearest-neighbor box [L]^d, for d,L≥2 and n=L^d, the answer is, up to logarithmic factors, nd^1/(p−1)L^p/(p−1) for 1<p<2 and ndL^2 for p≥2. On bounded-degree trees, an explicit rerooting-invariant parameter T_G determines the answer up to logarithmic factors; for arbitrary trees it gives upper and lower bounds that differ additionally by the maximum degree. If the volume conductance h(G)≥ h_0>0, then T_p(G,1/2)=Θ_p,h_0(nlog n) without a degree assumption. At p=∞, every connected graph satisfies T_∞(G,1/2)≥ c nD^2/Δ, where D and Δ are its diameter and maximum degree.
ER -