Arrow Research search

Author name cluster

Mark Jerrum

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

22 papers
2 author rows

Possible papers

22

SODA Conference 2017 Conference Paper

Random cluster dynamics for the Ising model is rapidly mixing

  • Heng Guo 0001
  • Mark Jerrum

We show for the first time that the mixing time of Glauber (single edge update) dynamics for the random cluster model at q = 2 is bounded by a polynomial in the size of the underlying graph. As a consequence, the Swendsen- Wang algorithm for the ferromagnetic Ising model at any temperature has the same polynomial mixing time bound.

Details

SODA Conference 2016 Conference Paper

On the switch Markov chain for perfect matchings

  • Martin E. Dyer
  • Mark Jerrum
  • Haiko Müller

We study a simple Markov chain, the switch chain, on the set of all perfect matchings in a bipartite graph. This Markov chain was proposed by Diaconis, Graham and Holmes as a possible approach to a sampling problem arising in Statistics. They considered several classes of graphs, and conjectured that the switch chain would mix rapidly for graphs in these classes. Here we settle their conjecture almost completely. We ask: for which graph classes is the Markov chain ergodic and for which is it rapidly mixing? We provide a precise answer to the ergodicity question and close bounds on the mixing question. We show for the first time that the mixing time of the switch chain is polynomial in the class of monotone graphs. This class was identified by Diaconis, Graham and Holmes as being of particular interest in the statistical setting.

Details

FOCS Conference 2002 Conference Paper

Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows

  • Mary Cryan
  • Martin E. Dyer
  • Leslie Ann Goldberg
  • Mark Jerrum
  • Russell A. Martin

We consider the problem of sampling almost uniformly from the set of contingency tables with given row and column sums, when the number of rows is a constant. (2002) have recently given a fully polynomial randomized approximation scheme (fpras) for the related counting problem, which only employs Markov chain methods indirectly. But they leave open the question as to whether a natural Markov chain on such tables mixes rapidly. Here we answer this question in the affirmative, and hence provide a very different proof of the main result of Cryan and Dyer. We show that the "2 /spl times/ 2 heat-bath" Markov chain is rapidly mixing. We prove this by considering first a heat-bath chain operating on a larger window. Using techniques developed by Morris and Sinclair (2002) (see also Morris (2002)) for the multidimensional knapsack problem, we show that this chain mixes rapidly. We then apply the comparison method of Diaconis and Saloff-Coste (1993) to show that the 2 /spl times/ 2 chain is rapidly mixing. As part of our analysis, we give the first proof that the 2 /spl times/ 2 chain mixes in time polynomial in the input size when both the number of rows and the number of columns is constant.

Details

FOCS Conference 2002 Conference Paper

Spectral Gap and log-Sobolev Constant for Balanced Matroids

  • Mark Jerrum
  • Jung-Bae Son

We compute tight lower bounds on the log-Sobolev constant of a class of inductively defined Markov chains, which contains the bases-exchange walks for balanced matroids studied by Feder and Mihail. As a corollary, we obtain improved upper bounds for the mixing time of a variety of Markov chains. An example: the "natural" random walk on spanning trees of a graph G as proposed by Broder - which has been studied by a number of authors - mixes in time O(mn log n), where n is the number of vertices of G and m the number of edges. This beats the best previous upper bound on this walk by a factor n/sup 2/.

Details

FOCS Conference 1999 Conference Paper

On Counting Independent Sets in Sparse Graphs

  • Martin E. Dyer
  • Alan M. Frieze
  • Mark Jerrum

We prove two results concerning approximate counting of independent sets in graphs with constant maximum degree /spl Delta/. The first result implies that the Monte-Carlo Markov chain technique is likely to fail if /spl Delta//spl ges/6. The second shows that no fully polynomial randomized approximation scheme can exist for /spl Delta//spl ges/25, unless P=NP under randomized reductions.

Details

FOCS Conference 1996 Conference Paper

Learning Linear Transformations

  • Alan M. Frieze
  • Mark Jerrum
  • Ravindran Kannan

We present a polynomial time algorithm to learn (in Valiant's PAC model) an arbitrarily oriented cube in n-space, given uniformly distributed sample points from it. In fact, we solve the more general problem of learning, in polynomial time, a linear (affine) transformation of a product distribution.

Details

FOCS Conference 1993 Conference Paper

Simulated Annealing for Graph Bisection

  • Mark Jerrum
  • Gregory B. Sorkin

We resolve in the affirmative a question of R. B. Boppana and T. Bui: whether simulated annealing can with high probability and in polynomial time, find the optimal bisection of a random graph an G/sub npr/ when p-r=(/spl Theta/n/sup /spl Delta/-2/) for /spl Delta//spl les/2. (The random graph model G/sub npr/ specifies a "planted" bisection of density r, separating two n/2-vertex subsets of slightly higher density p.) We show that simulated "annealing" at an appropriate fixed temperature (i. e. , the Metropolis algorithm) finds the unique smallest bisection in O(n/sup 2+/spl epsi//) steps with very high probability, provided /spl Delta/>11/6. (By using a slightly modified neighborhood structure, the number of steps can be reduced to O(n/sup 1+/spl epsi//).) We leave open the question of whether annealing is effective for /spl Delta/ in the range 3/2>

Details

FOCS Conference 1992 Conference Paper

A Mildly Exponential Approximation Algorithm for the Permanent

  • Mark Jerrum
  • Umesh V. Vazirani

An approximation algorithm for the permanent of an n*n 0, 1-matrix is presented. The algorithm is shown to have worst-case time complexity exp (0(n/sup 1/2/ log/sup 2/ n)). Asymptotically, this represents a considerable improvement over the best existing algorithm, which has worst-case time complexity of the form e/sup theta (n)/. >

Details

FOCS Conference 1982 Conference Paper

A Compact Representation for Permutation Groups

  • Mark Jerrum

An O(n2) space representation for permutation groups of degree n is presented. The representation can be constructed in time O(n5), and supports fast membership testing. Applications of the representation to the generation of systems of coset representatives, and of complete block systems, are discussed.

Details