Local Search with Correlated Randomness

arXiv:2607.17469v2 Announce Type: replace-cross 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<sle1, and Dge1. 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_. At and above it, the expected flip count is O_{k,r}(min{L^3,L/(s-s_)}), 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.

Source: arXiv cs.LG | 2026-09-30