Accueil

Prasad Tetali

  1. Tight Bounds for Mixing of the Swendsen-Wang Algorithm at the Potts Transition Point.

    Tue, 11/16/2010 - 16:01 — SomNambul
    Authors: Prasad Tetali, Christian Borgs, Jennifer T. Chayes
    Subjects: Probability
    Abstract

    We study two widely used algorithms for the Potts model on rectangular
    subsets of the hypercubic lattice Z^d - heat bath dynamics and the
    Swendsen-Wang algorithm - and prove that, under certain circumstances, the
    mixing in these algorithms is torpid or slow. In particular, we show that for
    heat bath dynamics throughout the region of phase coexistence, and for the
    Swendsen-Wang algorithm at the transition point, the mixing time in a box of
    side length L with periodic boundary conditions has upper and lower bounds
    which are exponential in L^{d-1}.

  2. Combinatorial approach to the interpolation method and scaling limits in sparse random graphs.

    Tue, 12/15/2009 - 16:01 — SomNambul
    Authors: Prasad Tetali, Mohsen Bayati, David Gamarnik
    Subjects: Probability
    Abstract

    We establish the existence of free energy limits for several sparse random
    hypergraph models corresponding to certain combinatorial models on
    Erd{\"o}s-R\'{e}nyi graph $\G(N,c/N)$ and random $r$-regular graph $\G(N,r)$.
    For a variety of models, including independent sets, MAX-CUT, Coloring and
    K-SAT, we prove that the free energy both at a positive and zero temperature,
    appropriately rescaled, converges to a limit as the size of the underlying
    graph diverges to infinity.

  3. Near-Optimal Sublinear Time Bounds for Distributed Random Walks.

    Wed, 11/18/2009 - 16:01 — SomNambul
    Authors: Prasad Tetali, Danupon Nanongkai, Atish Das Sarma, Gopal Pandurangan
    Subjects: and Cluster Computing, Distributed, Parallel
    Abstract

    We focus on the problem of performing random walks efficiently in a
    distributed network. Given bandwidth constraints, the goal is to minimize the
    number of rounds required to obtain a random walk sample on an undirected
    network. Despite the widespread use of random walks in distributed computing,
    most algorithms that compute a random walk sample of length $\ell$ naively,
    i.e., in $O(\ell)$ rounds.

  4. Phase Transition for the Mixing Time of the Glauber Dynamics for Coloring Regular Trees.

    Thu, 08/20/2009 - 23:06 — SomNambul
    Authors: Prasad Tetali, Juan C. Vera, Eric Vigoda, Linji Yang
    Subjects: Probability
    Abstract

    We prove that the mixing time of the Glauber dynamics for random
    $k$-colorings of the complete tree with branching factor $b$ undergoes a phase
    transition at $k=b(1+o_b(1))/\ln{b}$. Our main result shows nearly sharp bounds
    on the mixing time of the dynamics on the complete tree with $n$ vertices for
    $k=Cb/\ln{b}$ colors with constant $C$. For $C\geq 1$ we prove the mixing time
    is $O(n^{1+o_b(1)}\ln^2{n})$. On the other side, for $C< 1$ the mixing time
    experiences a slowing down, in particular, we prove it is $O(n^{1/C +
    o_b(1)}\ln^2{n})$ and $\Omega(n^{1/C-o_b(1)})$.

Math-arch

Syndicate content