Local Search with Correlated Randomness

Abstract

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 $\nu [w]\le DP[w{]}^s$ for every finite prefix $w$, where $P$ is an independent reference law, $0<s\le 1$, and $D\ge 1$. 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 probabilities $1$ and $\exp [-\Theta (n)]$ at the same linear deadline under the same source constraint. We identify a static priority rule that is optimal at every deadline and every $D$. For the standard local walk on a $k$-CNF with at least $r$ true literals per clause under some assignment, $k/2<r<k$, we determine the sharp source threshold $s_{\ast }$. At and above it, the expected flip count is $O_{k,r}(\min \{L^3,L/(s-s_{\ast })\})$, where $L=h+\log D+1$, $h$ is the initial Hamming distance to that assignment, and $L/0=\infty$. The bound allows arbitrary clause overlap and history-dependent clause selection. Matching instances admit one source forcing this delay with probability one for every selector. At criticality and fixed $D$, the delay is cubic despite a linear independent-source expectation. Variable-depth prefix covers, together with classical tree max-flow/min-cut, yield an exact criterion for restoring exponential tails by restarting on the same tape. We synthesize updates and restarts for explicit finite-state processes. Under a sufficient prefix guarantee, we also obtain noisy predecessor search with error at most $\eta$ and expected query count polynomial in the correct leaf's depth and $\log (D/\eta )$, without knowing the depth or tree height.