ﻻ يوجد ملخص باللغة العربية
We apply the power-of-two-choices paradigm to a random walk on a graph: rather than moving to a uniform random neighbour at each step, a controller is allowed to choose from two independent uniform random neighbours. We prove that this allows the controller to significantly accelerate the hitting and cover times in several natural graph classes. In particular, we show that the cover time becomes linear in the number $n$ of vertices on discrete tori and bounded degree trees, of order $mathcal{O}(n log log n)$ on bounded degree expanders, and of order $mathcal{O}(n (log log n)^2)$ on the ErdH{o}s-R{e}nyi random graph in a certain sparsely connected regime. We also consider the algorithmic question of computing an optimal strategy, and prove a dichotomy in efficiency between computing strategies for hitting and cover times.
Random factor graphs provide a powerful framework for the study of inference problems such as decoding problems or the stochastic block model. Information-theoretically the key quantity of interest is the mutual information between the observed facto
We consider the proportion of generalized visible lattice points in the plane visited by random walkers. Our work concerns the visible lattice points in random walks in three aspects: (1) generalized visibility along curves; (2) one random walker vis
This is the second in a series of articles devoted to showing that a typical covering map of large degree to a fixed, regular graph has its new adjacency eigenvalues within the bound conjectured by Alon for random regular graphs. The first main res
We study random walks on the giant component of the ErdH{o}s-Renyi random graph ${cal G}(n,p)$ where $p=lambda/n$ for $lambda>1$ fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Ko
We develop a framework for the rigorous analysis of focused stochastic local search algorithms. These are algorithms that search a state space by repeatedly selecting some constraint that is violated in the current state and moving to a random nearby