Yuval Peres

  1. All-Pairs Shortest Paths in $O(n^2)$ time with high probability.

    Authors: Yuval Peres, Benny Sudakov, Dimitry Sotnikov, Uri Zwick
    Subjects: Combinatorics
    Abstract

    We present an all-pairs shortest path algorithm whose running time on a
    complete directed graph on $n$ vertices whose edge weights are chosen
    independently and uniformly at random from $[0,1]$ is $O(n^2)$, in expectation
    and with high probability. This resolves a long standing open problem. The
    algorithm is a variant of the dynamic all-pairs shortest paths algorithm of
    Demetrescu and Italiano. The analysis relies on a proof that the number of
    \emph{locally shortest paths} in such randomly weighted graphs is $O(n^2)$, in
    expectation and with high probability.

  2. An isoperimetric inequality for the Wiener sausage.

    Authors: Yuval Peres, Perla Sousi
    Subjects: Probability
    Abstract

    Let $(\xi(s))_{s\geq 0}$ be a standard Brownian motion in $d\geq 1$
    dimensions and let $(D_s)_{s \geq 0}$ be a collection of open sets in $\R^d$.
    For each $s$, let $B_s$ be a ball centered at 0 with $\vol(B_s) = \vol(D_s)$.
    We show that $\E[\vol(\cup_{s \leq t}(\xi(s) + D_s))] \geq \E[\vol(\cup_{s \leq
    t}(\xi(s) + B_s))]$, for all $t$. In particular, this implies that the expected
    volume of the Wiener sausage increases when a drift is added to the Brownian
    motion.

  3. Hausdorff dimension for fractals invariant under the multiplicative integers.

    Authors: Yuval Peres, Boris Solomyak, Richard Kenyon
    Subjects: Dynamical Systems
    Abstract

    We consider subsets of the (symbolic) sequence space that are invariant under
    the action of the semigroup of multiplicative integers. A representative
    example is the collection of all 0-1 sequences $(x_k)$ such that $x_k x_{2k}=0$
    for all $k$. We compute the Hausdorff and Minkowski dimensions of these sets
    and show that they are typically different. The proof proceeds via a
    variational principle for multiplicative subshifts.

  4. Mobile Geometric Graphs: Detection, Coverage and Percolation.

    Authors: Yuval Peres, Perla Sousi, Alistair Sinclair, Alexandre Stauffer
    Subjects: Probability
    Abstract

    We consider the following dynamic Boolean model introduced by van den Berg,
    Meester and White (1997). At time 0, let the nodes of the graph be a Poisson
    point process in R^d with constant intensity and let each node move
    independently according to Brownian motion. At any time t, we put an edge
    between every pair of nodes if their distance is at most r.

  5. Collisions of Random Walks.

    Authors: Yuval Peres, Martin T. Barlow, Perla Sousi
    Subjects: Probability
    Abstract

    A recurrent graph $G$ has the infinite collision property if two independent
    random walks on $G$, started at the same point, collide infinitely often a.s.
    We give a simple criterion in terms of Green functions for a graph to have this
    property, and use it to prove that a critical Galton-Watson tree with finite
    variance conditioned to survive, the incipient infinite cluster in $\Z^d$ with
    $d \ge 19$ and the uniform spanning tree in $\Z^2$ all have the infinite
    collision property.

  6. Brownian motion with variable drift can be space-filling.

    Authors: Yuval Peres, Tonći Antunović, Brigitta Vermesi
    Subjects: Probability
    Abstract

    For $d \geq 2$ let $B$ be standard $d$-dimensional Brownian motion. For any
    $\alpha < 1/d$ we construct an $\alpha$-H\"{o}lder continuous function $f
    \colon [0,1] \to \mathbb{R}^d$ so that the range of $B-f$ covers an open set.
    This strengthens a result of Graversen (1982) and answers a question of Le Gall
    (1988).

  7. Harmonic maps on amenable groups and a diffusive lower bound for random walks.

    Authors: Yuval Peres, James R. Lee
    Subjects: Probability
    Abstract

    We prove that on any infinite, connected, locally finite, transitive graph G,
    the probability of the random walk being within $\eps \sqrt{t}$ of the origin
    after t steps is at most $O(\eps)$. A similar statement holds for finite
    graphs, up to the relaxation time of the walk. Our approach uses non-constant
    equivariant harmonic mappings taking values in a Hilbert space. For the special
    case of discrete, amenable groups, we present a more explicit proof of the
    Mok-Korevaar-Schoen theorem on existence of such harmonic maps by constructing
    them from the heat flow on a Folner set.

  8. Thick Points of the Gaussian Free Field.

    Authors: Yuval Peres, Xiaoyu Hu, Jason Miller
    Subjects: Probability
    Abstract

    Let $U \subseteq \C$ be a bounded domain with smooth boundary and let $F$ be
    an instance of the continuum Gaussian free field on $U$ with respect to the
    Dirichlet inner product $\int_U \nabla f(x) \cdot \nabla g(x) dx$. The set
    $T(a;U)$ of $a$-thick points of $F$ consists of those $z \in U$ such that the
    average of $F$ on a disk of radius $r$ centered at $z$ has growth $\sqrt{a/\pi}
    \log \tfrac{1}{r}$ as $r \to 0$.

  9. Mixing time for the Ising model: a uniform lower bound for all graphs.

    Authors: Yuval Peres, Jian Ding
    Subjects: Probability
    Abstract

    Consider Glauber dynamics for the Ising model on a graph of $n$ vertices.
    Hayes and Sinclair showed that the mixing time for this dynamics is at least
    $n\log n/f(\Delta)$, where $\Delta$ is the maximum degree and $f(\Delta) =
    \Theta(\Delta \log^2 \Delta)$. Their result applies to more general spin
    systems, and in that generality, they showed that some dependence on $\Delta$
    is necessary. In this paper, we focus on the ferromagnetic Ising model and
    prove that the mixing time of Glauber dynamics on any $n$-vertex graph is at
    least $(1/4+o(1))n \log n$.

  10. Mixing time for the Ising model: a uniform lower bound for all graphs.

    Authors: Yuval Peres, Jian Ding
    Subjects: Probability
    Abstract

    Consider Glauber dynamics for the Ising model on a graph of $n$ vertices.
    Hayes and Sinclair showed that the mixing time for this dynamics is at least
    $n\log n/f(\Delta)$, where $\Delta$ is the maximum degree and $f(\Delta) =
    \Theta(\Delta \log^2 \Delta)$. Their result applies to more general spin
    systems, and in that generality, they showed that some dependence on $\Delta$
    is necessary. In this paper, we focus on the ferromagnetic Ising model and
    prove that the mixing time of Glauber dynamics on any $n$-vertex graph is at
    least $(1/4+o(1))n \log n$.

  11. Mixing time of near-critical random graphs.

    Authors: Yuval Peres, Jian Ding, Eyal Lubetzky
    Subjects: Probability
    Abstract

    Let $C_1$ be the largest component of the Erd\H{o}s-R\'enyi random graph
    $G(n,p)$. The mixing time of random walk on $C_1$ in the strictly supercritical
    regime, $p=c/n$ with fixed $c>1$, was shown to have order $\log^2 n$ by
    Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In
    the critical window, $p=(1+\epsilon)/n$ where $\lambda=\epsilon^3 n$ is
    bounded, Nachmias and Peres proved that the mixing time on $C_1$ is of order
    $n$.

  12. Mixing time of near-critical random graphs.

    Authors: Yuval Peres, Jian Ding, Eyal Lubetzky
    Subjects: Probability
    Abstract

    Let $C_1$ be the largest component of the Erd\H{o}s-R\'enyi random graph
    $G(n,p)$. The mixing time of random walk on $C_1$ in the strictly supercritical
    regime, $p=c/n$ with fixed $c>1$, was shown to have order $\log^2 n$ by
    Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald. In
    the critical window, $p=(1+\epsilon)/n$ where $\lambda=\epsilon^3 n$ is
    bounded, Nachmias and Peres proved that the mixing time on $C_1$ is of order
    $n$.

  13. Reconstruction on Trees: Exponential Moment Bounds for Linear Estimators.

    Authors: Yuval Peres, Sebastien Roch
    Subjects: Probability
    Abstract

    Consider a Markov chain $(\xi_v)_{v \in V} \in [k]^V$ on the infinite $b$-ary
    tree $T = (V,E)$ with irreducible edge transition matrix $M$, where $b \geq 2$,
    $k \geq 2$ and $[k] = \{1,...,k\}$. We denote by $L_n$ the level-$n$ vertices
    of $T$. Assume $M$ has a real second-largest (in absolute value) eigenvalue
    $\lambda$ with corresponding real eigenvector $\nu \neq 0$.

Syndicate content