# Local Search with Correlated Randomness

arXiv: https://arxiv.org/abs/2607.17469 · HTML: https://mlsanity.com/paper/2607.17469/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 29 references that are in the map.
- First posted on arXiv 20 Jul 2026.

## Builds on (most cited first, 5 of 5)

- [Pointwise Generalization in Deep Neural Networks](https://mlsanity.com/paper/2605.18598/) (2026)
- [Noisy (Binary) Searching: Simple, Fast and Correct](https://mlsanity.com/paper/2107.05753/) (2021)
- [Affine Monotonic and Risk-Sensitive Models in Dynamic Programming](https://mlsanity.com/paper/1608.01393/) (2016)
- [Risk sensitive optimal stopping](https://mlsanity.com/paper/1912.02486/) (2019)
- [Bellman-sufficient Information Complexity](https://mlsanity.com/paper/2606.11171/) (2026)

## Abstract (arXiv)

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]≤ DP[w]s for every finite prefix w, where P is an independent reference law, 0<s≤1, and D≥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_*. At and above it, the expected flip count is Ok,r(minL3,L/(s-s_*)), where L=h+log D+1, h is the initial Hamming distance to that assignment, and L/0=∞. 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 η and expected query count polynomial in the correct leaf's depth and log(D/η), without knowing the depth or tree height.