{"id":"arxiv/2607.17469","url":"https://arxiv.org/abs/2607.17469","tags":["cs.CC","cond-mat.stat-mech","cs.LG","math.CO","math.PR"],"score":0,"title":"Local Search with Correlated Randomness","domain":"cs.CC","source":"arxiv","authors":["Yunbei Xu"],"reviews":0,"subject":"cs.CC","summary":"How much does an algorithm's running-time distribution under independent randomness reveal about its behavior when independence is no longer guaranteed? We study sources satisfying $ν[w]\\le DP[w]^s$ for every finite prefix $w$, where $P$ is an independent reference law, $0<s\\le1$, and $D\\ge1$. The constraint controls complete-prefix probabilities while allowing individual choices to be predictable, even fully determined by the past. For retry tasks, all deterministic history-dependent selectors have the same independent-source running-time law. Yet two orders have worst-case failure…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-20","reactions":{}}