Boosting search by rare events

Abstract

Randomized search algorithms for hard combinatorial problems exhibit a large variability of performances. We study the different types of rare events which occur in such out-of-equilibrium stochastic processes and we show how they cooperate in determining the final distribution of running times. As a byproduct of our analysis we show how search algorithms are optimized by random restarts.

4 pages, 3 eps figures. References updated

References in corpus (1)

• Core percolation in random graphs: a critical phenomena analysis

Cited by in corpus (100)

• Stochastic Resetting and Applications
• First Passage Under Restart
• First order transition for the optimal search time of Lévy flights with resetting
• Optimal stochastic restart renders fluctuations in first passage times universal
• Diffusion under time-dependent resetting
• Run and tumble particle under resetting: a renewal approach
• Diffusion in a potential landscape with stochastic resetting
• Diffusion with resetting in arbitrary spatial dimension
• Dynamical transition in the temporal relaxation of stochastic processes under resetting
• Diffusion with stochastic resetting at power-law times
• Fluctuating interfaces subject to stochastic resetting
• The Michaelis-Menten reaction scheme as a unified approach towards the optimal restart problem
• Stochastic resetting: A (very) brief review
• Restart could optimize the probability of success in a Bernoulli trial
• Resetting processes with non-instanteneous return
• The inspection paradox in stochastic resetting
• Scaled Brownian motion with renewal resetting
• First passage of a particle in a potential under stochastic resetting: a vanishing transition of optimal resetting rate
• Optimization by Quantum Annealing: Lessons from hard 3-SAT cases
• Diffusion with resetting in a logarithmic potential
• Random walks on networks with stochastic resetting
• Random walk with random resetting to the maximum
• Symmetric Exclusion Process under Stochastic Resetting
• Stochastic resetting with stochastic returns using external trap
• Ising model with stochastic resetting
• Run-and-Tumble particles in Two-dimensions under Stochastic Resetting
• First passage under restart for discrete space and time: application to one dimensional confined lattice random walks
• Invariants of motion with stochastic resetting and space-time coupled returns
• Active Brownian Motion in two-dimensions under Stochastic Resetting
• Stochastic resetting in underdamped Brownian motion
• Intermittent resetting potentials
• Mean first passage time of active Brownian particle in one dimension
• On large deviation properties of Erdos-Renyi random graphs
• Relaxation and Metastability in the RandomWalkSAT search procedure
• Stochastic resetting by a random amplitude
• Extremal statistics for stochastic resetting systems
• Solving satisfiability problems by fluctuations: The dynamics of stochastic local search algorithms
• Space-dependent diffusion with stochastic resetting: A first-passage study
• Diffusions conditioned on occupation measures
• Random acceleration process under stochastic resetting
• Diffusion with Resetting Inside a Circle
• Resetting with stochastic return through linear confining potential
• Convergence of large deviation estimators
• First-passage Brownian functionals with stochastic resetting
• Number of distinct sites visited by a resetting random walker
• Stochastic Resetting for Enhanced Sampling
• Statistical mechanics of the vertex-cover problem
• Statistical Mechanics of maximal independent sets
• Mean-performance of sharp restart I: Statistical roadmap
• Diffusion with Local Resetting and Exclusion
• Diffusion processes with Gamma-distributed resetting and non-instantaneous returns
• Mitigating long queues and waiting times with service resetting
• Mitigating long transient time in deterministic systems by resetting
• Time to reach the maximum for a stationary stochastic process
• Universal framework for record ages under restart
• Fick-Jacobs description and first passage dynamics for diffusion in a channel under stochastic resetting
• Brownian motion under non-instantaneous resetting in higher dimensions
• First passage of a diffusing particle under stochastic resetting in bounded domains with spherical symmetry
• Thermodynamic work of partial resetting
• General approach to stochastic resetting
• Resetting mediated navigation of active Brownian searcher in a homogeneous topography
• Diffusion with two resetting points
• The cavity method for large deviations
• Non-linear diffusion with stochastic resetting
• Mean-performance of Sharp Restart II: Inequality Roadmap
• Tail-behavior roadmap for sharp restart
• Discrete-time random walks and Lévy flights on arbitrary networks: when resetting becomes advantageous?
• Dynamical phase transition in the occupation fraction statistics for non-crossing Brownian particles
• Exponentially hard problems are sometimes polynomial, a large deviation analysis of search algorithms for the random Satisfiability problem, and its application to stop-and-restart resolutions
• Searching for clusters of targets under stochastic resetting
• Autonomous Ratcheting by Stochastic Resetting
• Extremal statistics for a resetting Brownian motion before its first-passage time
• Optimal Measurement Protocols in Quantum Zeno Effect
• Optimizing Leapover Lengths of Lévy Flights with Resetting
• Effects of mortality on stochastic search processes with resetting
• Entropy rate of random walks on complex networks under stochastic resetting
• Comparing the roles of time overhead and spatial dimensions on optimal resetting rate vanishing transitions, in Brownian processes with potential bias and stochastic resetting
• Queues with resetting: a perspective
• Optimal conditions for first passage of jump processes with resetting
• First passage in discrete-time absorbing Markov chains under stochastic resetting
• Optimal resetting strategies for search processes in heterogeneous environments
• Stochastic representation of processes with resetting
• Random search with resetting in heterogeneous environments
• Universal performance bounds of restart
• Partial versus total resetting for Lévy flights in d dimensions: similarities and discrepancies
• Non-homogeneous random walks with stochastic resetting: an application to the Gillis model
• Symmetric Exclusion Process under Stochastic Power-law Resetting
• Critical behaviour of combinatorial search algorithms, and the unitary-propagation universality class
• Active Brownian particle under stochastic position and orientation resetting in a harmonic trap
• Mean first passage time of active fluctuating membrane with stochastic resetting
• Autocorrelation functions and ergodicity in diffusion with stochastic resetting
• Optimization and Physics: On the satisfiability of random Boolean formulae
• Local resetting with geometric confinement
• Stationary state of harmonic chains driven by boundary resetting
• Gaussian Process and Levy Walk under Stochastic Non-instantaneous Resetting and Stochastic Rest
• Ising Model with Power Law Resetting
• Gradient dynamics in reinforcement learning
• Restart method and exponential acceleration of random 3-SAT instances resolutions: a large deviation analysis of the Davis-Putnam-Loveland-Logemann algorithm
• The one-dimensional telegraphic process with noninstantaneous stochastic resetting
• Exact fluctuation and long-range correlations in a single-file model under resetting