Mark Jerrum

TCS Journal 2017 Journal Article

Functional clones and expressibility of partition functions

• Andrei Bulatov
• Leslie Ann Goldberg
• Mark Jerrum
• David Richerby
• Stanislav Živný

We study functional clones, which are sets of non-negative pseudo-Boolean functions (functions { 0, 1 } k → R ≥ 0 ) closed under (essentially) multiplication, summation and limits. Functional clones naturally form a lattice under set inclusion and are closely related to counting Constraint Satisfaction Problems (CSPs). We identify a sublattice of interesting functional clones and investigate the relationships and properties of the functional clones in this sublattice.

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.

STOC Conference 2017 Conference Paper

Uniform sampling through the Lovasz local lemma

• Heng Guo 0001
• Mark Jerrum
• Jingcheng Liu 0001

We propose a new algorithmic framework, called “partial rejection sampling”, to draw samples exactly from a product distribution, conditioned on none of a number of bad events occurring. Our framework builds (perhaps surprising) new connections between the variable framework of the Lovász Local Lemma and some clas- sical sampling algorithms such as the “cycle-popping” algorithm for rooted spanning trees by Wilson. Among other applications, we discover new algorithms to sample satisfying assignments of k-CNF formulas with bounded variable occurrences.

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.

TCS Journal 2016 Journal Article

The complexity of counting locally maximal satisfying assignments of Boolean CSPs

• Leslie Ann Goldberg
• Mark Jerrum

We investigate the computational complexity of the problem of counting the locally maximal satisfying assignments of a Constraint Satisfaction Problem (CSP) over the Boolean domain { 0, 1 }. A satisfying assignment is locally maximal if any new assignment which is obtained from it by changing a 0 to a 1 is unsatisfying. For each constraint language Γ, # LocalMaxCSP ( Γ ) denotes the problem of counting the locally maximal satisfying assignments, given an input CSP with constraints in Γ. We give a complexity dichotomy for the problem of exactly counting the locally maximal satisfying assignments and a complexity trichotomy for the problem of approximately counting them. Relative to the problem # CSP ( Γ ), which is the problem of counting all satisfying assignments, the locally maximal version can sometimes be easier but never harder. This finding contrasts with the recent discovery that approximately counting locally maximal independent sets in a bipartite graph is harder (under the usual complexity-theoretic assumptions) than counting all independent sets.

I&C Journal 2008 Journal Article

Inapproximability of the Tutte polynomial

• Leslie Ann Goldberg
• Mark Jerrum

The Tutte polynomial of a graph G is a two-variable polynomial T ( G; x, y ) that encodes many interesting properties of the graph. We study the complexity of the following problem, for rationals x and y: take as input a graph G, and output a value which is a good approximation to T ( G; x, y ). Jaeger et al. have completely mapped the complexity of exactly computing the Tutte polynomial. They have shown that this is #P-hard, except along the hyperbola ( x - 1 ) ( y - 1 ) = 1 and at four special points. We are interested in determining for which points ( x, y ) there is a fully polynomial randomised approximation scheme (FPRAS) for T ( G; x, y ). Under the assumption RP ≠ NP, we prove that there is no FPRAS at ( x, y ) if ( x, y ) is in one of the half-planes x < - 1 or y < - 1 (excluding the easy-to-compute cases mentioned above). Two exceptions to this result are the half-line x < - 1, y = 1 (which is still open) and the portion of the hyperbola ( x - 1 ) ( y - 1 ) = 2 corresponding to y < - 1 which we show to be equivalent in difficulty to approximately counting perfect matchings. We give further intractability results for ( x, y ) in the vicinity of the origin. A corollary of our results is that, under the assumption RP ≠ NP, there is no FPRAS at the point ( x, y ) = ( 0, 1 - λ ) when λ > 2 is a positive integer. Thus, there is no FPRAS for counting nowhere-zero λ flows for λ > 2. This is an interesting consequence of our work since the corresponding decision problem is in P for example for λ = 6. Although our main concern is to distinguish regions of the Tutte plane that admit an FPRAS from those that do not, we also note that the latter regions exhibit different levels of intractability. At certain points ( x, y ), for example the integer points on the x-axis, or any point in the positive quadrant, there is a randomised approximation scheme for T ( G; x, y ) that runs in polynomial time using an oracle for an NP predicate. On the other hand, we identify a region of points ( x, y ) at which even approximating T ( G; x, y ) is as hard as #P.

STOC Conference 2007 Conference Paper

Inapproximability of the Tutte polynomial

• Leslie Ann Goldberg
• Mark Jerrum

The Tutte polynomial of a graph G is a two-variable polynomial T(G;x,y) that encodes many interesting properties of the graph. We study the complexityof the following problem, for rationals x and y: take as input a graph G , and output a value which is a good approximation to T(G;x,y). We are interested in determining for which points (x,y) there is a fullypolynomial randomised approximation scheme (FPRAS) for T(G;x,y). Our main contribution is a substantial widening of the region known to benon-FPRASable.

I&C Journal 2004 Journal Article

Counting and sampling H-colourings

• Martin Dyer
• Leslie Ann Goldberg
• Mark Jerrum

For counting problems in #Pwhich are “essentially self-reducible, ” it is known that sampling and approximate counting are equivalent. However, many problems of interest do not have such a structure and there is already some evidence that this equivalence does not hold for the whole of #P. An intriguing example is the class of H-colouring problems, which have recently been the subject of much study, and their natural generalisation to vertex- and edge-weighted versions. Particular cases of the counting-to-sampling reduction have been observed, but it has been an open question as to how far these reductions might extend to any H and a general graph G. Here we give the first completely general counting-to-sampling reduction. For every fixed H, we show that the problem of approximately determining the partition function of weighted H-colourings can be reduced to the problem of sampling these colourings from an approximately correct distribution. In particular, any rapidly-mixing Markov chain for sampling H-colourings can be turned into an FPRAS for counting H-colourings.

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.

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/.

STOC Conference 2001 Conference Paper

A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries

• Mark Jerrum
• Alistair Sinclair
• Eric Vigoda

We present a fully-polynomial randomized approximation scheme for computing the permanent of an arbitrary matrix with non-negative entries.

SODA Conference 2000 Conference Paper

An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract)

• Martin E. Dyer
• Leslie Ann Goldberg
• Catherine S. Greenhill
• Mark Jerrum
• Michael Mitzenmacher

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.

I&C Journal 1997 Journal Article

A Quasi-polynomial-time Algorithm for Sampling Words from a Context-Free Language

• Vivek Gore
• Mark Jerrum
• Sampath Kannan
• Z. Sweedyk
• Steve Mahaney

A quasi-polynomial-time algorithm is presented for sampling almost uniformly at random from then-slice of the languageL(G) generated by an arbitrary context-free grammarG. (Then-slice of a languageLover an alphabetΣis the subsetL∩Σ n of words of length exactlyn.) The time complexity of the algorithm isε −2(n |G|) O(log n)where the parameterεbounds the variation of the output distribution from uniform, and |G| is a natural measure of the size of grammarG. The algorithm applies to a class of language sampling problems that includes slices of context-free languages as a proper subclass. For the restricted case of homogeneous languages expressed by regular expressions without Kleene-star, a truly polynomial-time algorithm is presented.

SODA Conference 1997 Conference Paper

Randomly Sampling Molecules

• Leslie Ann Goldberg
• Mark Jerrum

STOC Conference 1997 Conference Paper

The Swendsen-Wang Process Does Not Always Mix Rapidly

• Vivek Gore
• Mark Jerrum

TCS Journal 1996 Journal Article

A polynomial algorithm for deciding bisimilarity of normed context-free processes

• Yoram Hirshfeld
• Mark Jerrum
• Faron Moller

The previous best upper bound on the complexity of deciding bisimilarity between normed context-free processes is due to Huynh and Tian (1994), who put the problem in Σ 2 P = NP NP: their algorithm guesses a proof of equivalence and validates this proof in polynomial time using oracles freely answering questions which are in NP. In this paper we improve on this result by describing a polynomial-time algorithm which solves this problem. As a corollary, we have a polynomial algorithm for the equivalence problem for simple grammars.

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.

FOCS Conference 1994 Conference Paper

A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes

• Yoram Hirshfeld
• Mark Jerrum
• Faron Moller

A polynomial-time procedure is presented for deciding bisimilarity of normed context-free processes. It follows as a corollary that language equivalence of simple context-free grammars is decidable in polynomial time. >

SODA Conference 1994 Conference Paper

Approximately Counting Hamilton Cycles in Dense Graphs

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

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>

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)/. >

TCS Journal 1990 Journal Article

Fast uniform generation of regular graphs

• Mark Jerrum
• Alistair Sinclair

An algorithm is presented which randomly selects a labelled graph with specified vertex degrees from a distribution which is arbitrarily close to uniform. The algorithm is based on simulation of a rapidly convergent stochastic process, and runs in polynomial time for a wide class of degree sequences, including all regular sequences and all n-vertex sequences with no degree exceeding √n/2. The algorithm can be extended to cover the selection of a graph with given degree sequence which avoids a specified set of edges. One consequence of this extension is the existence of a polynomial-time algorithm for selecting an f-factor in a sufficiently dense graph. A companion algorithm for counting degree-constrained graphs is also presented; this algorithm has exactly the same range of validity as the one for selection.

I&C Journal 1989 Journal Article

Approximate counting, uniform generation and rapidly mixing Markov chains

• Alistair Sinclair
• Mark Jerrum

The paper studies effective approximate solutions to combinatorial counting and unform generation problems. Using a technique based on the simulation of ergodic Markov chains, it is shown that, for self-reducible structures, almost uniform generation is possible in polynomial time provided only that randomised approximate counting to within some arbitrary polynomial factor is possible in polynomial time. It follows that, for self-reducible structures, polynomial time randomised algorithms for counting to within factors of the form (1 + n −β ) are available either for all β ϵ R or for no β ϵ R. A substantial part of the paper is devoted to investigating the rate of convergence of finite ergodic Markov chains, and a simple but powerful characterisation of rapid convergence for a broad class of chains based on a structural property of the underlying graph is established. Finally, the general techniques of the paper are used to derive an almost uniform generation procedure for labelled graphs with a given degree sequence which is valid over a much wider range of degrees than previous methods: this in turn leads to randomised approximate counting algorithms for these graphs with very good asymptotic behaviour.

STOC Conference 1988 Conference Paper

Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version)

• Mark Jerrum
• Alistair Sinclair

The permanent of an n x n matrix A with 0-1 entries a ij is defined by per ( A ) = Σ/σ Π/ n -1/ i = ο a i σ( i ) , where the sum is over all permutations σ of [ n ] = {0, …, n - 1}. Evaluating per ( A ) is equivalent to counting perfect matchings (1-factors) in the bipartite graph G = ( V 1 , V 2 , E ), where V 1 = V 2 = [ n ] and ( i , j ) ∈ E iff a ij = 1. The permanent function arises naturally in a number of fields, including algebra, combinatorial enumeration and the physical sciences, and has been an object of study by mathematicians for many years (see [14] for background). Despite considerable effort, and in contrast with the syntactically very similar determinant, no efficient procedure for computing this function is known.

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.