Consensus time for asynchronous $\ell^p$ relaxation: graph dependence
We study the asynchronous $\ell^p$ relaxation introduced by Amir, Nazarov, and Peres: at each step, a uniformly chosen vertex minimizes its incident $\ell^p$ energy. For the profile $f_t$ after $t$ updates, let $$ \mathsf T_p(G,1/2):= \sup_{\lVert f_0\rVert_\infty\le1} \mathbb{E}\bigl[\min\{t\ge0:\operatorname{osc}(f_t)\le1/2\}\bigr]. $$ For $1 0$, then $\mathsf T_p(G,1/2)=Θ_{p,h_0}(n\log n)$ without a degree assumption. At $p=\infty$, every connected graph satisfies $\mathsf T_\infty(G,1/2)\ge c nD^2/Δ$, where $D$ and $Δ$ are its diameter and maximum degree.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.03856
curl -X POST /api/v1/records/arxiv/2609.03856/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.03856/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'