Local Search with Correlated Randomness
Abstract
The running-time distribution of a randomized algorithm is computed under independent randomness, but independence is rarely what a source guarantees. We study sources ν satisfying ν[w]≤ DP[w]s for every finite prefix w of the random tape, where P is an independent reference law, 0<s≤1, and D≥1; individual choices may be predictable, even determined by the past. The worst-case probability of any closed tape event E is exactly min{1,DCs(E)}, where Cs(E) is the infimum cost of covering E by prefixes of varying depth, a tree max-flow/min-cut identity that makes worst-case survival probabilities exact and optimizable over the algorithm's choices. Three applications follow. For n tasks on one machine, 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[−Θ(n)]; a static priority rule is optimal at every deadline. For the standard local walk on a k-CNF with an assignment that satisfies a majority of each clause, we determine the sharp source threshold s*. Below s*, on some instances a single admissible source forces nontermination however clauses are selected; at s*, with fixed D, the expected number of flips is at most cubic in the initial Hamming distance, against linear under independence, with matching worst-case instances; and any fixed margin above s* restores linear dependence on the distance. Third, verified backtracking for noisy predecessor search remains correct under a sufficiently strong bound on the comparison errors. In every setting the algorithm may also restart, which supplies no fresh randomness; restarting restores exponential tails exactly when the nontermination event has a prefix cover of cost below one.
Related
- textsc{Athanor}: local search over abstract constraint specifications
- Small-LCM Distinct Covering Systems via Segmented Local Search
- Local Search for Almost-Spanning Square Grids in Erdős--Rényi Random Graphs
- GPU Parallel Pareto Local Search for Multi-objective QUBO
- Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint Assignment
BibTeX
@misc{xu2026local,
title = {{Local Search with Correlated Randomness}},
author = {Yunbei Xu},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2607.17469},
eprint = {2607.17469},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2607.17469},
}
RIS
TY - UNPB
TI - Local Search with Correlated Randomness
AU - Yunbei Xu
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2607.17469
UR - https://arxiv.org/abs/2607.17469
AB - The running-time distribution of a randomized algorithm is computed under independent randomness, but independence is rarely what a source guarantees. We study sources ν satisfying ν[w]≤ DP[w]^s for every finite prefix w of the random tape, where P is an independent reference law, 0<s≤1, and D≥1; 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, a tree max-flow/min-cut identity that makes worst-case survival probabilities exact and optimizable over the algorithm's choices. Three applications follow. For n tasks on one machine, 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[−Θ(n)]; a static priority rule is optimal at every deadline. For the standard local walk on a k-CNF with an assignment that satisfies a majority of each clause, we determine the sharp source threshold s_*. Below s_*, on some instances a single admissible source forces nontermination however clauses are selected; at s_*, with fixed D, the expected number of flips is at most cubic in the initial Hamming distance, against linear under independence, with matching worst-case instances; and any fixed margin above s_* restores linear dependence on the distance. Third, verified backtracking for noisy predecessor search remains correct under a sufficiently strong bound on the comparison errors. In every setting the algorithm may also restart, which supplies no fresh randomness; restarting restores exponential tails exactly when the nontermination event has a prefix cover of cost below one.
ER -