Главная

Eric Vigoda

  1. A Deterministic Polynomial-time Approximation Scheme for Counting Knapsack Solutions.

    Ср, 08/11/2010 - 15:01 — SomNambul
    Authors: Eric Vigoda, Daniel Stefankovic, Santosh Vempala
    Subjects: Data Structures and Algorithms
    Abstract

    Given n elements with nonnegative integer weights w1,..., wn and an integer
    capacity C, we consider the counting version of the classic knapsack problem:
    find the number of distinct subsets whose weights add up to at most the given
    capacity. We give a deterministic algorithm that estimates the number of
    solutions to within relative error 1+-eps in time polynomial in n and 1/eps
    (fully polynomial approximation scheme). More precisely, our algorithm takes
    time O(n^3 (1/eps) log (n/eps)).

  2. Phase Transition for Glauber Dynamics for Independent Sets on Regular Trees.

    Чт, 07/15/2010 - 15:01 — SomNambul
    Authors: Juan C. Vera, Eric Vigoda, Linji Yang, Daniel Stefankovic, Ricardo Restrepo
    Subjects: Probability
    Abstract

    We study the effect of boundary conditions on the relaxation time of the
    Glauber dynamics for the hard-core model on the tree. The hard-core model is
    defined on the set of independent sets weighted by a parameter $\lambda$,
    called the activity. The Glauber dynamics is the Markov chain that updates a
    randomly chosen vertex in each step.

  3. Reconstruction for Colorings on Trees.

    Втр, 12/01/2009 - 16:01 — SomNambul
    Authors: Eric Vigoda, Nayantara Bhatnagar, Juan Vera, Dror Weitz
    Subjects: Probability
    Abstract

    Consider $k$-colorings of the complete tree of depth $\ell$ and branching
    factor $\Delta$. If we fix the coloring of the leaves, as $\ell$ tends to
    $\infty$, for what range of $k$ is the root uniformly distributed over all $k$
    colors? This corresponds to the threshold for uniqueness of the infinite-volume
    Gibbs measure. It is straightforward to show the existence of colorings of the
    leaves which ``freeze'' the entire tree when $k\le\Delta+1$. For
    $k\geq\Delta+2$, Jonasson proved the root is ``unbiased'' for any fixed
    coloring of the leaves and thus the Gibbs measure is unique.

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

    Чт, 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

RSS-материал