Mark Jerrum

ORCID

Publication Activity (10 Years)

Years Active: 1982-2024
Publications (10 Years): 44

Top Venues

CoRR

SIAM J. Comput.

J. Comput. Syst. Sci.

ACM Trans. Comput. Theory

Publications

Mark Jerrum
-free graphs. CoRR (2024)
Weiming Feng, Heng Guo, Mark Jerrum, Jiaheng Wang
A simple polynomial-time approximation algorithm for the total variation distance between two product distributions. TheoretiCS 2 (2023)
Heng Guo, Mark Jerrum
Counting Vertices of Integral Polytopes Defined by Facets. Discret. Comput. Geom. 70 (3) (2023)
Weiming Feng, Heng Guo, Mark Jerrum, Jiaheng Wang
A simple polynomial-time approximation algorithm for the total variation distance between two product distributions. SOSA (2023)
Konrad Anand, Mark Jerrum
via Weak Spatial Mixing. CoRR (2023)
Weiming Feng, Heng Guo, Mark Jerrum, Jiaheng Wang
A simple polynomial-time approximation algorithm for total variation distances between product distributions. CoRR (2022)
Konrad Anand, Mark Jerrum
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing. SIAM J. Comput. 51 (4) (2022)
Konrad Anand, Mark Jerrum
Perfect Sampling in Infinite Spin Systems Via Strong Spatial Mixing. SIAM J. Comput. 51 (3) (2022)
Martin E. Dyer, Marc Heinrich, Mark Jerrum, Haiko Müller
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs. Comb. Probab. Comput. 30 (6) (2021)
Mark Jerrum
Fundamentals of Partial Rejection Sampling. CoRR (2021)
Heng Guo, Mark Jerrum
Approximately counting bases of bicircular matroids. Comb. Probab. Comput. 30 (1) (2021)
Martin E. Dyer, Mark Jerrum, Haiko Müller, Kristina Vuskovic
Counting Weighted Independent Sets beyond the Permanent. SIAM J. Discret. Math. 35 (2) (2021)
Konrad Anand, Mark Jerrum
Perfect Sampling in Infinite Spin Systems via Strong Spatial Mixing. CoRR (2021)
Mark Jerrum, Tamás Makai
The Size of the Giant Joint Component in a Binomial Random Double Graph. Electron. J. Comb. 28 (1) (2021)
Heng Guo, Mark Jerrum
Counting vertices of integer polytopes defined by facets. CoRR (2021)
Martin E. Dyer, Marc Heinrich, Mark Jerrum, Haiko Müller
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs. CoRR (2020)
Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda
Random Walks on Small World Networks. ACM Trans. Algorithms 16 (3) (2020)
Heng Guo, Mark Jerrum, Jingcheng Liu
Uniform Sampling Through the Lovász Local Lemma. J. ACM 66 (3) (2019)
Leslie Ann Goldberg, Mark Jerrum
Approximating Pairwise Correlations in the Ising Model. ACM Trans. Comput. Theory 11 (4) (2019)
Martin E. Dyer, Mark Jerrum, Haiko Müller, Kristina Vuskovic
Counting weighted independent sets beyond the permanent. CoRR (2019)
Heng Guo, Mark Jerrum
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. SIAM J. Comput. 48 (3) (2019)
Heng Guo, Mark Jerrum
Perfect simulation of the Hard Disks Model by Partial Rejection Sampling. CoRR (2018)
Heng Guo, Mark Jerrum
Approximately counting bases of bicircular matroids. CoRR (2018)
Heng Guo, Mark Jerrum
Perfect Simulation of the Hard Disks Model by Partial Rejection Sampling. ICALP (2018)
Leslie Ann Goldberg, Mark Jerrum
Approximating Pairwise Correlations in the Ising Model. CoRR (2018)
Heng Guo, Mark Jerrum
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability. ICALP (2018)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
-Colorings. ACM Trans. Comput. Theory 9 (2) (2017)
Heng Guo, Mark Jerrum
A simple FPRAS for bi-directed reachability. CoRR (2017)
Andrei Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný
Functional clones and expressibility of partition functions. Theor. Comput. Sci. 687 (2017)
Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda
Random Walks on Small World Networks. CoRR (2017)
Mark Jerrum, Kitty Meeks
The parameterised complexity of counting even and odd induced subgraphs. Comb. 37 (5) (2017)
Martin E. Dyer, Mark Jerrum, Haiko Müller
On the Switch Markov Chain for Perfect Matchings. J. ACM 64 (2) (2017)
Ivona Bezáková, Leslie Ann Goldberg, Mark Jerrum
Computational Counting (Dagstuhl Seminar 18341). Dagstuhl Reports 7 (8) (2017)
Heng Guo, Mark Jerrum, Jingcheng Liu
Uniform sampling through the Lovasz local lemma. STOC (2017)
Heng Guo, Mark Jerrum
Random cluster dynamics for the Ising model is rapidly mixing. SODA (2017)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Approximately Counting H-Colorings is $\#\mathrm{BIS}$-Hard. SIAM J. Comput. 45 (3) (2016)
Martin E. Dyer, Mark Jerrum, Haiko Müller
On the switch Markov chain for perfect matchings. SODA (2016)
Leslie Ann Goldberg, Mark Jerrum
A complexity trichotomy for approximately counting list H-colourings. CoRR (2016)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
A Complexity Trichotomy for Approximately Counting List H-Colourings. ICALP (2016)
Leslie Ann Goldberg, Mark Jerrum
The complexity of counting locally maximal satisfying assignments of Boolean CSPs. Theor. Comput. Sci. 634 (2016)
Andrei A. Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivný
Functional Clones and Expressibility of Partition Functions. CoRR (2016)
Heng Guo, Mark Jerrum, Jingcheng Liu
Uniform Sampling through the Lovász Local Lemma. CoRR (2016)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region. J. Comput. Syst. Sci. 82 (5) (2016)
Heng Guo, Mark Jerrum
Random cluster dynamics for the Ising model is rapidly mixing. CoRR (2016)
Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby
The complexity of approximating conservative counting CSPs. J. Comput. Syst. Sci. 81 (1) (2015)
Mark Jerrum, Kitty Meeks
The parameterised complexity of counting connected subgraphs and graph motifs. J. Comput. Syst. Sci. 81 (4) (2015)
John D. Faben, Mark Jerrum
The Complexity of Parity Graph Homomorphism: An Initial Investigation. Theory Comput. 11 (2015)
Leslie Ann Goldberg, Mark Jerrum
A complexity classification of spin systems with an external field. Proc. Natl. Acad. Sci. USA 112 (43) (2015)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard. ICALP (1) (2015)
Mark Jerrum, Kitty Meeks
Some Hard Families of Parameterized Counting Problems. ACM Trans. Comput. Theory 7 (3) (2015)
Martin E. Dyer, Mark Jerrum, Haiko Müller
On the switch Markov chain for perfect matchings. CoRR (2015)
Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan
Approximating the partition function of planar two-state spin systems. J. Comput. Syst. Sci. 81 (1) (2015)
Leslie Ann Goldberg, Mark Jerrum
The complexity of Boolean #MaximalCSP. CoRR (2015)
Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum
Approximately Counting H-Colourings is #BIS-Hard. CoRR (2015)
Leslie Ann Goldberg, Mark Jerrum
The Complexity of Approximately Counting Tree Homomorphisms. ACM Trans. Comput. Theory 6 (2) (2014)
Mark Jerrum, Kitty Meeks
The parameterised complexity of counting even and odd induced subgraphs. CoRR (2014)
Leslie Ann Goldberg, Mark Jerrum
The Complexity of Computing the Sign of the Tutte Polynomial. SIAM J. Comput. 43 (6) (2014)
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Stefankovic, Eric Vigoda
#BIS-Hardness for 2-Spin Systems on Bipartite Bounded Degree Graphs in the Tree Non-uniqueness Region. APPROX-RANDOM (2014)
Leslie Ann Goldberg, Mark Jerrum
The Complexity of Approximately Counting Tree Homomorphisms CoRR (2013)
Mark Jerrum, Kitty Meeks
The Parameterised Complexity of Counting Connected Subgraphs. CoRR (2013)
Mark Jerrum, Kitty Meeks
Some hard classes of parameterised counting problems. CoRR (2013)
John D. Faben, Mark Jerrum
The complexity of parity graph homomorphism: an initial investigation. CoRR (2013)
Leslie Ann Goldberg, Mark Jerrum
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. SIAM J. Comput. 42 (3) (2013)
Jin-Yi Cai, Leslie Ann Goldberg, Heng Guo, Mark Jerrum
Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs. CoRR (2013)
Leslie Ann Goldberg, Mark Jerrum
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. J. Comput. Syst. Sci. 79 (1) (2013)
Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby
The complexity of approximating conservative counting CSPs. STACS (2013)
Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, Pascal Koiran
Computational Counting (Dagstuhl Seminar 13031). Dagstuhl Reports 3 (1) (2013)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan
The expressibility of functions on the boolean domain, with applications to counting CSPs. J. ACM 60 (5) (2013)
Leslie Ann Goldberg, Mark Jerrum
The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation). ICALP (1) (2012)
Leslie Ann Goldberg, Mark Jerrum
Approximating the partition function of the ferromagnetic potts model. J. ACM 59 (5) (2012)
Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby
The complexity of approximating conservative counting CSPs CoRR (2012)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby
The complexity of weighted and unweighted #CSP. J. Comput. Syst. Sci. 78 (2) (2012)
Leslie Ann Goldberg, Mark Jerrum
Inapproximability of the Tutte polynomial of a planar graph. Comput. Complex. 21 (4) (2012)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
Log-supermodular functions, functional clones and counting CSPs. STACS (2012)
Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan
Approximating the partition function of planar two-state spin systems CoRR (2012)
Leslie Ann Goldberg, Mark Jerrum
The Complexity of Computing the Sign of the Tutte Polynomial (and consequent #P-hardness of Approximation) CoRR (2012)
Leslie Ann Goldberg, Mark Jerrum
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. ICALP (1) (2011)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
Log-supermodular functions, functional clones and counting CSPs CoRR (2011)
Leslie Ann Goldberg, Mark Jerrum
A Counterexample to rapid mixing of the Ge-Stefankovic Process CoRR (2011)
Leslie Ann Goldberg, Mark Jerrum
A polynomial-time algorithm for estimating the partition function of the ferromagnetic Ising model on a regular matroid CoRR (2010)
Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby
The complexity of weighted and unweighted #CSP CoRR (2010)
Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
A Complexity Dichotomy For Hypergraph Partition Functions. Comput. Complex. 19 (4) (2010)
Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum
10481 Abstracts Collection - Computational Counting. Computational Counting (2010)
Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
An approximation trichotomy for Boolean #CSP. J. Comput. Syst. Sci. 76 (3-4) (2010)
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley
A Complexity Dichotomy for Partition Functions with Mixed Signs. SIAM J. Comput. 39 (7) (2010)
Mark Jerrum
Constraint satisfaction problems and computational complexity: technical persepctive. Commun. ACM 53 (9) (2010)
Leslie Ann Goldberg, Mark Jerrum
Approximating the Partition Function of the Ferromagnetic Potts Model. ICALP (1) (2010)
Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum
10481 Executive Summary - Computational Counting. Computational Counting (2010)
Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
The mixing time of Glauber dynamics for coloring regular trees. Random Struct. Algorithms 36 (4) (2010)
Leslie Ann Goldberg, Mark Jerrum
Approximating the partition function of the ferromagnetic Potts model CoRR (2010)
Leslie Ann Goldberg, Mark Jerrum
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials CoRR (2010)
Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
The Complexity of Weighted Boolean #CSP. SIAM J. Comput. 38 (5) (2009)
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley
A Complexity Dichotomy for Partition Functions with Mixed Signs. STACS (2009)
Leslie Ann Goldberg, Mark Jerrum
Inapproximability of the Tutte polynomial of a planar graph CoRR (2009)
Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
Dobrushin Conditions and Systematic Scan. Comb. Probab. Comput. 17 (6) (2008)
Leslie Ann Goldberg, Mark Jerrum
Inapproximability of the Tutte polynomial. Inf. Comput. 206 (7) (2008)
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley
A complexity dichotomy for partition functions with mixed signs CoRR (2008)
Martin E. Dyer, Mark Jerrum, Marek Karpinski
08201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. Design and Analysis of Randomized and Approximation Algorithms (2008)
Leslie Ann Goldberg, Mark Jerrum, Marek Karpinski
The Mixing Time of Glauber Dynamics for Colouring Regular Trees CoRR (2008)
Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum
A complexity dichotomy for hypergraph partition functions CoRR (2008)

Mark Jerrum.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Mark Jerrum