Random Clocks on Computation Paths]{Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?
Abstract
We watch a computation only at moments chosen by a random clock that can leap ahead, pause, or step back, and we count looks rather than steps. How far can such a clock reliably see with polynomially many looks, and does stepping back help? Rare long leaps reach exponential and doubly exponential time, with infinitely many levels between polynomial and exponential time. A clock that tends to fall back sees only the start of the input, and below polynomial time we find infinitely many incomparable levels. Stepping back can help decisively. For clocks whose long leaps occur only at rare positions, no forward-only clock goes beyond polynomial time, while even single steps back raise the reach to exponential time. Stepping back cannot help, however, when the clock's leaps ignore its position.
Related
- Saturated directed spaces and generalized clocks
- Hölder Selections under Stieltjes Clocks: Uniform Disconnectedness and Jump Dominance
- Optimal Investment and Consumption in Financial Markets with Integrated Variance Clocks
- Nonreciprocal Spherical Attention and Retrieval: Sharp Coarsening Clocks and Certified Score Correction
- Selections of Set-Valued Maps under Stieltjes Clocks: Regularity, Variation, and Atomic Structure
BibTeX
@misc{didehvar2026random,
title = {{Random Clocks on Computation Paths]Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?}},
author = {Farzad Didehvar and Saman Farhat},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.25830},
eprint = {2610.25830},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.25830},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Random Clocks on Computation Paths]{Random Clocks on Computation Paths: How Far Can They Reach, and When Does Stepping Back Help?
AU - Farzad Didehvar
AU - Saman Farhat
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.25830
UR - https://arxiv.org/abs/2610.25830
AB - We watch a computation only at moments chosen by a random clock that can leap ahead, pause, or step back, and we count looks rather than steps. How far can such a clock reliably see with polynomially many looks, and does stepping back help? Rare long leaps reach exponential and doubly exponential time, with infinitely many levels between polynomial and exponential time. A clock that tends to fall back sees only the start of the input, and below polynomial time we find infinitely many incomparable levels. Stepping back can help decisively. For clocks whose long leaps occur only at rare positions, no forward-only clock goes beyond polynomial time, while even single steps back raise the reach to exponential time. Stepping back cannot help, however, when the clock's leaps ignore its position.
ER -