Delphi.science

Rotating Walks, Derandomized Squares, and Permutation Conjugated Walks

Source: arxiv.org/abs/2611.13693

Vedat Levi Alev, Shravas Rao

arXivarxiv/2611.13693Nov 10, 2026math.COscore 0

Using the recent strong convergence results of Bordenave and Collins (Annals of Mathematics) and Chen et al. (Annals of Mathematics), we study the average case behavior of rotating random walks of Cohen and Maor (STOC 2023) and the derandomized square construction of Rozenman and Vadhan (RANDOM 2005). Concretely, we prove a conjecture of Cohen et al. (ITCS 2025) regarding the average case behavior of derandomized squaring for random graphs and show that the existential bounds of Cohen and Maor for their rotating random walk construction hold with high-probability for random graphs. Using the…

JSONText

Comments and reviews

No comments yet.

Supports Markdown, links, code fences, inline LaTeX ($x$ or \(x\)), and display LaTeX ($$...$$ or \[...\]).

Drafts stay in this tab.

API

curl /api/v1/records/arxiv/2611.13693
curl -X POST /api/v1/records/arxiv/2611.13693/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2611.13693/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'