Mark Jerrum

From MaRDI portal


List of research outcomes

This list is not complete and representing at the moment only items from zbMATH Open and arXiv. We are working on additional sources - please check back here soon!

PublicationDate of PublicationType
Fundamentals of partial rejection sampling
Probability Surveys
2024-09-10Paper
A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
TheoretiCS
2024-07-03Paper
A simple polynomial-time approximation algorithm for the total variation distance between two product distributions
 
2024-05-14Paper
Counting vertices of integral polytopes defined by facets
Discrete & Computational Geometry
2023-10-12Paper
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs
Combinatorics, Probability and Computing
2023-03-30Paper
Perfect Sampling of $q$-Spin Systems on $\mathbb Z^2$ via Weak Spatial Mixing
 
2023-02-15Paper
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing
SIAM Journal on Computing
2022-08-12Paper
Perfect simulation of the hard disks model by partial rejection sampling
 
2021-07-28Paper
scientific article; zbMATH DE number 7375995 (Why is no real title available?)
 
2021-07-28Paper
Perfect Sampling in Infinite Spin Systems via Strong Spatial Mixing
 
2021-06-30Paper
Counting weighted independent sets beyond the permanent
SIAM Journal on Discrete Mathematics
2021-06-28Paper
Approximately counting bases of bicircular matroids
Combinatorics, Probability and Computing
2021-06-15Paper
Counting constraint satisfaction problems
 
2021-06-15Paper
Fundamentals of Partial Rejection Sampling
 
2021-06-14Paper
Perfect simulation of the hard disks model by partial rejection sampling
Annales de l'Institut Henri Poincaré D. Combinatorics, Physics and their Interactions (AIHPD)
2021-06-09Paper
Random walks on small world networks
ACM Transactions on Algorithms
2021-05-03Paper
The size of the giant joint component in a binomial random double graph
The Electronic Journal of Combinatorics
2021-02-16Paper
The complexity of computing the sign of the Tutte polynomial
SIAM Journal on Computing
2020-05-31Paper
Approximating pairwise correlations in the Ising model
ACM Transactions on Computation Theory
2019-12-16Paper
A Complexity Trichotomy for Approximately Counting List H -Colorings
ACM Transactions on Computation Theory
2019-12-06Paper
Uniform sampling through the Lovász local lemma
Journal of the ACM
2019-11-21Paper
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability
SIAM Journal on Computing
2019-09-02Paper
The parameterised complexity of counting even and odd induced subgraphs
Combinatorica
2019-02-01Paper
On the switch Markov chain for perfect matchings
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms
2018-07-16Paper
Random cluster dynamics for the Ising model is rapidly mixing
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms
2018-07-16Paper
Random cluster dynamics for the Ising model is rapidly mixing
The Annals of Applied Probability
2018-06-29Paper
On the switch Markov chain for perfect matchings
Journal of the ACM
2018-05-17Paper
A complexity trichotomy for approximately counting list \(H\)-colourings
 
2017-12-19Paper
Uniform sampling through the Lovász local lemma
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
2017-08-17Paper
Functional clones and expressibility of partition functions
Theoretical Computer Science
2017-06-13Paper
\#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
 
2017-03-22Paper
A complexity classification of spin systems with an external field
Proceedings of the National Academy of Sciences
2017-02-16Paper
The complexity of approximating conservative counting CSPs
 
2017-01-30Paper
Some hard families of parameterized counting problems
ACM Transactions on Computation Theory
2016-11-10Paper
Approximately counting \(H\)-colorings is \(\#\)BIS-hard
SIAM Journal on Computing
2016-06-01Paper
The complexity of counting locally maximal satisfying assignments of Boolean CSPs
Theoretical Computer Science
2016-05-18Paper
\(\#\)BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
Journal of Computer and System Sciences
2016-04-18Paper
Approximately counting \(H\)-colourings is \(\#\mathrm{BIS}\)-hard
Automata, Languages, and Programming
2015-10-27Paper
The complexity of approximately counting tree homomorphisms
ACM Transactions on Computation Theory
2015-09-03Paper
The complexity of parity graph homomorphism: an initial investigation
Theory of Computing
2015-08-21Paper
scientific article; zbMATH DE number 6472592 (Why is no real title available?)
 
2015-08-14Paper
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries
Proceedings of the thirty-third annual ACM symposium on Theory of computing
2015-02-27Paper
The parameterised complexity of counting connected subgraphs and graph motifs
Journal of Computer and System Sciences
2015-02-20Paper
Approximating the partition function of planar two-state spin systems
Journal of Computer and System Sciences
2014-09-22Paper
The complexity of approximating conservative counting CSPs
Journal of Computer and System Sciences
2014-09-22Paper
The expressibility of functions on the Boolean domain, with applications to counting CSPs
Journal of the ACM
2014-02-17Paper
Approximating the partition function of the ferromagnetic Potts model
Journal of the ACM
2014-02-17Paper
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
SIAM Journal on Computing
2013-09-25Paper
The complexity of computing the sign of the Tutte polynomial (and consequent \#P-hardness of approximation)
Automata, Languages, and Programming
2013-08-12Paper
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials
Journal of Computer and System Sciences
2013-02-21Paper
Inapproximability of the Tutte polynomial of a planar graph
Computational Complexity
2012-12-27Paper
Log-supermodular functions, functional clones and counting CSPs
 
2012-08-23Paper
A counterexample to rapid mixing of the Ge-Stefankovic process
Electronic Communications in Probability
2012-06-22Paper
The complexity of weighted and unweighted \(\#\)CSP
Journal of Computer and System Sciences
2012-05-11Paper
A complexity dichotomy for partition functions with mixed signs
 
2012-04-24Paper
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid
Lecture Notes in Computer Science
2011-07-06Paper
A Complexity Dichotomy for Partition Functions with Mixed Signs
SIAM Journal on Computing
2011-04-04Paper
A complexity dichotomy for hypergraph partition functions
Computational Complexity
2011-02-18Paper
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
Journal of the ACM
2011-02-01Paper
The mixing time of Glauber dynamics for coloring regular trees
Random Structures & Algorithms
2010-11-24Paper
Approximating the partition function of the ferromagnetic Potts model
Lecture Notes in Computer Science
2010-09-07Paper
Markov chain comparison
Probability Surveys
2010-06-29Paper
An approximation trichotomy for Boolean \#CSP
Journal of Computer and System Sciences
2010-05-25Paper
The Complexity of Weighted Boolean #CSP
SIAM Journal on Computing
2009-11-06Paper
Matrix norms and rapid mixing for spin systems
The Annals of Applied Probability
2009-04-02Paper
Dobrushin Conditions and Systematic Scan
Combinatorics, Probability and Computing
2009-03-04Paper
Inapproximability of the Tutte polynomial
 
2009-01-05Paper
Inapproximability of the Tutte polynomial
Information and Computation
2008-08-14Paper
Improved approximation algorithms for MAX \(k\)-CUT and MAX BISECTION
 
2008-06-02Paper
Dobrushin Conditions and Systematic Scan
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
2007-08-28Paper
scientific article; zbMATH DE number 5168339 (Why is no real title available?)
 
2007-06-28Paper
Two remarks concerning balanced matroids
Combinatorica
2007-05-08Paper
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
SIAM Journal on Computing
2007-03-27Paper
The Complexity of Ferromagnetic Ising with Local Fields
Combinatorics, Probability and Computing
2007-03-20Paper
Systematic scan for sampling colorings
The Annals of Applied Probability
2006-06-29Paper
On the approximation of one Markov chain by another
Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete
2006-03-21Paper
scientific article; zbMATH DE number 2151251 (Why is no real title available?)
 
2005-04-04Paper
Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains
The Annals of Applied Probability
2005-03-21Paper
A Bound on the Capacity of Backoff and Acknowledgment-Based Protocols
SIAM Journal on Computing
2005-02-21Paper
Counting and sampling \(H\)-colourings
Information and Computation
2004-11-23Paper
The relative complexity of approximate counting problems
Algorithmica
2004-09-22Paper
scientific article; zbMATH DE number 2019624 (Why is no real title available?)
 
2003-12-17Paper
scientific article; zbMATH DE number 2019625 (Why is no real title available?)
 
2003-12-17Paper
The computational complexity of two‐state spin systems
Random Structures & Algorithms
2003-11-10Paper
scientific article; zbMATH DE number 1885142 (Why is no real title available?)
 
2003-03-19Paper
Convergence of the Iterated Prisoner's Dilemma Game
Combinatorics, Probability and Computing
2003-03-17Paper
On Counting Independent Sets in Sparse Graphs
SIAM Journal on Computing
2002-09-29Paper
The ‘Burnside Process’ Converges Slowly
Combinatorics, Probability and Computing
2002-05-14Paper
scientific article; zbMATH DE number 1670534 (Why is no real title available?)
 
2002-01-06Paper
scientific article; zbMATH DE number 1281304 (Why is no real title available?)
 
2001-11-13Paper
scientific article; zbMATH DE number 1670864 (Why is no real title available?)
 
2001-11-11Paper
An extension of path coupling and its application to the Glauber dynamics for graph colorings
SIAM Journal on Computing
2001-06-21Paper
scientific article; zbMATH DE number 1559583 (Why is no real title available?)
 
2001-03-01Paper
scientific article; zbMATH DE number 1445357 (Why is no real title available?)
 
2000-10-23Paper
Counting Unlabelled Subtrees of a Tree is #P-complete
LMS Journal of Computation and Mathematics
2000-09-25Paper
scientific article; zbMATH DE number 1301969 (Why is no real title available?)
 
2000-09-24Paper
scientific article; zbMATH DE number 1405656 (Why is no real title available?)
 
2000-07-10Paper
Randomly Sampling Molecules
SIAM Journal on Computing
2000-03-19Paper
The Swendsen-Wang process does not always mix rapidly
Journal of Statistical Physics
2000-03-16Paper
The Metropolis algorithm for graph bisection
Discrete Applied Mathematics
2000-03-13Paper
scientific article; zbMATH DE number 1263268 (Why is no real title available?)
 
1999-11-03Paper
On Approximately Counting Colorings of Small Degree Graphs
SIAM Journal on Computing
1999-10-28Paper
scientific article; zbMATH DE number 1256668 (Why is no real title available?)
 
1999-04-22Paper
scientific article; zbMATH DE number 1246228 (Why is no real title available?)
 
1999-01-27Paper
Approximately Counting Hamilton Paths and Cycles in Dense Graphs
SIAM Journal on Computing
1998-09-20Paper
An $\Omega(\sqrt{\,\log\log n}\,)$ Lower Bound for Routing in Optical Networks
SIAM Journal on Computing
1998-09-20Paper
A quasi-polynomial-time algorithm for sampling words from a context-free language
Information and Computation
1997-12-17Paper
Improved approximation algorithms for MAX \(k\)-cut and MAX BISECTION
Algorithmica
1997-10-09Paper
scientific article; zbMATH DE number 1003265 (Why is no real title available?)
 
1997-04-23Paper
A polynomial algorithm for deciding bisimilarity of normed context-free processes
Theoretical Computer Science
1997-02-27Paper
A mildly exponential approximation algorithm for the permanent
Algorithmica
1997-02-18Paper
Generating and Counting Hamilton Cycles in Random Regular Graphs
Journal of Algorithms
1996-12-16Paper
A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes
Mathematical Structures in Computer Science
1996-11-18Paper
A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
Random Structures & Algorithms
1996-03-14Paper
scientific article; zbMATH DE number 782052 (Why is no real title available?)
 
1996-03-13Paper
scientific article; zbMATH DE number 850077 (Why is no real title available?)
 
1996-03-04Paper
scientific article; zbMATH DE number 822898 (Why is no real title available?)
 
1996-01-16Paper
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers
Machine Learning
1995-10-29Paper
Simple translation-invariant concepts are hard to learn
Information and Computation
1995-10-09Paper
scientific article; zbMATH DE number 747036 (Why is no real title available?)
 
1995-08-27Paper
An analysis of Monte Carlo algorithm for estimating the permanent
Combinatorica
1995-07-23Paper
scientific article; zbMATH DE number 475376 (Why is no real title available?)
 
1995-06-12Paper
Counting trees in a graph is \(\# \text{P}\)-complete
Information Processing Letters
1994-10-13Paper
Three-dimensional Statistical Data Security Problems
SIAM Journal on Computing
1994-03-27Paper
Polynomial-Time Approximation Algorithms for the Ising Model
SIAM Journal on Computing
1993-12-20Paper
scientific article; zbMATH DE number 177833 (Why is no real title available?)
 
1993-05-18Paper
Large Cliques Elude the Metropolis Process
Random Structures & Algorithms
1993-01-16Paper
Fast uniform generation of regular graphs
Theoretical Computer Science
1990-01-01Paper
Approximate counting, uniform generation and rapidly mixing Markov chains
Information and Computation
1989-01-01Paper
Approximating the Permanent
SIAM Journal on Computing
1989-01-01Paper
scientific article; zbMATH DE number 4083048 (Why is no real title available?)
 
1988-01-01Paper
scientific article; zbMATH DE number 4172979 (Why is no real title available?)
 
1988-01-01Paper
Random generation of combinatorial structures from a uniform distribution
Theoretical Computer Science
1986-01-01Paper
A compact representation for permutation groups
Journal of Algorithms
1986-01-01Paper
scientific article; zbMATH DE number 3978386 (Why is no real title available?)
 
1985-01-01Paper
The complexity of finding minimum-length generator sequences
Theoretical Computer Science
1985-01-01Paper
Families of Fixed Degree Graphs for Processor Interconnection
IEEE Transactions on Computers
1984-01-01Paper
scientific article; zbMATH DE number 3900155 (Why is no real title available?)
 
1984-01-01Paper
Some Exact Complexity Results for Straight-Line Computations over Semirings
Journal of the ACM
1982-01-01Paper
Glauber dynamics for the hard-core model on bounded-degree $H$-free graphs
 
N/APaper


Research outcomes over time


This page was built for person: Mark Jerrum