Local Search with Correlated Randomness

원문 초록

The running-time distribution of a randomized algorithm is computed under independent randomness, but independence is rarely what a source guarantees. We study sources $\nu$ with $\nu[w]\le DP[w]^s$ for every finite prefix $w$ of the tape, where $P$ is an independent reference law, $0<s\le1$, and $D\ge1$; individual choices may be predictable, even determined by the past. The worst-case probability of any closed tape event $E$ is exactly $\min\{1,DC_s(E)\}$, where $C_s(E)$ is the infimum cost of covering $E$ by prefixes of varying depth. This tree max-flow/min-cut identity makes worst-case probabilities exact and optimizable. Three applications follow. In scheduling, $n$ tasks on one machine are each retried until the next random symbol lies in its success set; every schedule has the same makespan distribution under independent randomness, yet under our constraint two fixed orders miss a linear deadline with worst-case probabilities $1$ and $\exp[-\Theta(n)]$, and a static priority rule is optimal at every deadline. For the standard local walk on a $k$-CNF with an assignment satisfying a majority of each clause, we find the sharp source threshold $s_*$: below it, on some instances one admissible source forces nontermination for every clause selection; at it, with fixed $D$, the expected number of flips is at most cubic in the initial distance, against linear under independence, with matching instances at distances up to a constant fraction of the number of variables; a fixed margin above it restores linear dependence. For noisy predecessor search with prefix-bounded comparison errors, verified backtracking attains any prescribed error probability at or above a source threshold whose sharpness we leave open, with the same cubic-to-linear query bounds. Restarting on the shared tape restores exponential tails exactly when the nontermination event has a prefix cover of cost below one.