ترغب بنشر مسار تعليمي؟ اضغط هنا

Local Access to Random Walks

94   0   0.0 ( 0 )
 نشر من قبل Amartya Shankha Biswas
 تاريخ النشر 2021
  مجال البحث الهندسة المعلوماتية
والبحث باللغة English




اسأل ChatGPT حول البحث

For a graph $G$ on $n$ vertices, naively sampling the position of a random walk of at time $t$ requires work $Omega(t)$. We desire local access algorithms supporting $text{position}(G,s,t)$ queries, which return the position of a random walk from some start vertex $s$ at time $t$, where the joint distribution of returned positions is $1/text{poly}(n)$ close to the uniform distribution over such walks in $ell_1$ distance. We first give an algorithm for local access to walks on undirected regular graphs with $widetilde{O}(frac{1}{1-lambda}sqrt{n})$ runtime per query, where $lambda$ is the second-largest eigenvalue in absolute value. Since random $d$-regular graphs are expanders with high probability, this gives an $widetilde{O}(sqrt{n})$ algorithm for $G(n,d)$, which improves on the naive method for small numbers of queries. We then prove that no that algorithm with sub-constant error given probe access to random $d$-regular graphs can have runtime better than $Omega(sqrt{n}/log(n))$ per query in expectation, obtaining a nearly matching lower bound. We further show an $Omega(n^{1/4})$ runtime per query lower bound even with an oblivious adversary (i.e. when the query sequence is fixed in advance). We then show that for families of graphs with additional group theoretic structure, dramatically better results can be achieved. We give local access to walks on small-degree abelian Cayley graphs, including cycles and hypercubes, with runtime $text{polylog}(n)$ per query. This also allows for efficient local access to walks on $text{polylog}$ degree expanders. We extend our results to graphs constructed using the tensor product (giving local access to walks on degree $n^epsilon$ graphs for any $epsilon in (0,1]$) and Cartesian product.



قيم البحث

اقرأ أيضاً

In this paper, we introduce the on-line Viterbi algorithm for decoding hidden Markov models (HMMs) in much smaller than linear space. Our analysis on two-state HMMs suggests that the expected maximum memory used to decode sequence of length $n$ with $m$-state HMM can be as low as $Theta(mlog n)$, without a significant slow-down compared to the classical Viterbi algorithm. Classical Viterbi algorithm requires $O(mn)$ space, which is impractical for analysis of long DNA sequences (such as complete human genome chromosomes) and for continuous data streams. We also experimentally demonstrate the performance of the on-line Viterbi algorithm on a simple HMM for gene finding on both simulated and real DNA sequences.
Under the Strong Exponential Time Hypothesis, an integer linear program with $n$ Boolean-valued variables and $m$ equations cannot be solved in $c^n$ time for any constant $c < 2$. If the domain of the variables is relaxed to $[0,1]$, the associated linear program can of course be solved in polynomial time. In this work, we give a natural algorithmic bridging between these extremes of $0$-$1$ and linear programming. Specifically, for any subset (finite union of intervals) $E subset [0,1]$ containing ${0,1}$, we give a random-walk based algorithm with runtime $O_E((2-text{measure}(E))^ntext{poly}(n,m))$ that finds a solution in $E^n$ to any $n$-variable linear program with $m$ constraints that is feasible over ${0,1}^n$. Note that as $E$ expands from ${0,1}$ to $[0,1]$, the runtime improves smoothly from $2^n$ to polynomial. Taking $E = [0,1/k) cup (1-1/k,1]$ in our result yields as a corollary a randomized $(2-2/k)^{n}text{poly}(n)$ time algorithm for $k$-SAT. While our approach has some high level resemblance to Sch{o}nings beautiful algorithm, our general algorithm is based on a more sophisticated random walk that incorporates several new ingredients, such as a multiplicative potential to measure progress, a judicious choice of starting distribution, and a time varying distribution for the evolution of the random walk that is itself computed via an LP at each step (a solution to which is guaranteed based on the minimax theorem). Plugging the LP algorithm into our earlier polymorphic framework yields fast exponential algorithms for any CSP (like $k$-SAT, $1$-in-$3$-SAT, NAE $k$-SAT) that admit so-called `threshold partial polymorphisms.
70 - Peter Nandori , Zeyu Shen 2016
We prove that the local time process of a planar simple random walk, when time is scaled logarithmically, converges to a non-degenerate pure jump process. The convergence takes place in the Skorokhod space with respect to the $M1$ topology and fails to hold in the $J1$ topology.
The aim of this paper is the study of the strong local survival property for discrete-time and continuous-time branching random walks. We study this property by means of an infinite dimensional generating function G and a maximum principle which, we prove, is satisfied by every fixed point of G. We give results about the existence of a strong local survival regime and we prove that, unlike local and global survival, in continuous time, strong local survival is not a monotone property in the general case (though it is monotone if the branching random walk is quasi transitive). We provide an example of an irreducible branching random walk where the strong local property depends on the starting site of the process. By means of other counterexamples we show that the existence of a pure global phase is not equivalent to nonamenability of the process, and that even an irreducible branching random walk with the same branching law at each site may exhibit non-strong local survival. Finally we show that the generating function of a irreducible BRW can have more than two fixed points; this disproves a previously known result.
302 - Leonardo T. Rolla 2015
Lecture Notes. Minicourse given at the workshop Activated Random Walks, DLA, and related topics at IMeRA-Marseille, March 2015.
التعليقات
جاري جلب التعليقات جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
mircosoft-partner

هل ترغب بارسال اشعارات عن اخر التحديثات في شمرا-اكاديميا