Mark Jerrum

Q: What Schools Are Affiliated With Mark Jerrum

Mark Jerrum is affiliated with the following schools: University of Edinburgh, Queen Mary University of London

Mark Jerrum's AcademicInfluence.com Rankings

Mark Jerrum

Computer Science

#561

World Rank

#581

Historical Rank

Theoretical Computer Science

#15

World Rank

#15

Historical Rank

computer-science Degrees

Mark Jerrum

Mathematics

#2146

World Rank

#3357

Historical Rank

Graph Theory

#85

World Rank

#93

Historical Rank

Measure Theory

#1621

World Rank

#2000

Historical Rank

mathematics Degrees

Download Badge

Computer Science
Mathematics

Why Is Mark Jerrum Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Mark Richard Jerrum is a British computer scientist and computational theorist. Jerrum received his Ph.D. in computer science 'On the complexity of evaluating multivariate polynomials' in 1981 from University of Edinburgh under the supervision of Leslie Valiant. He is professor of pure mathematics at Queen Mary, University of London.

(See a Problem?)

Mark Jerrum's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

Random Generation of Combinatorial Structures from a Uniform Distribution (1986) (1022)
Approximating the Permanent (1989) (821)
Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains (1987) (794)
A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries (2004) (694)
Polynomial-Time Approximation Algorithms for the Ising Model (1993) (553)
The Markov chain Monte Carlo method: an approach to approximate counting and integration (1996) (541)
Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION (1995) (369)
Large Cliques Elude the Metropolis Process (1992) (327)
A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph (1995) (323)
A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries (2001) (269)
Conductance and the rapid mixing property for Markov chains: the approximation of permanent resolved (1988) (218)
Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers (1993) (183)
On counting independent sets in sparse graphs (1999) (178)
Improved approximation algorithms for MAXk-CUT and MAX BISECTION (1997) (158)
The Metropolis Algorithm for Graph Bisection (1998) (147)
A Polynomial Algorithm for Deciding Bisimilarity of Normed Context-Free Processes (1994) (146)
Counting, Sampling and Integrating: Algorithms and Complexity (2003) (145)
The Complexity of Finding Minimum-Length Generator Sequences (1985) (143)
On the relative complexity of approximate counting problems (2000) (135)
The Relative Complexity of Approximate Counting Problems (2000) (134)
Some Exact Complexity Results for Straight-Line Computations over Semirings (1982) (126)
Fast Uniform Generation of Regular Graphs (1990) (119)
Two-dimensional monomer-dimer systems are computationally intractable (1987) (114)
A Complexity Dichotomy for Partition Functions with Mixed Signs (2008) (106)
A compact representation for permutation groups (1982) (105)
Three-Dimensional Statistical Data Security Problems (1994) (103)
The Swendsen-Wang process does not always mix rapidly (1997) (101)
Elementary bounds on Poincaré and log-Sobolev constants for decomposable Markov chains (2004) (94)
A polynomial-time algorithm for deciding bisimulation equivalence of normed Basic Parallel Processes (1994) (93)
Simulated annealing for graph bisection (1993) (92)
Inapproximability of the Tutte polynomial (2006) (88)
The Complexity of Weighted Boolean #CSP (2007) (88)
Approximating the partition function of the ferromagnetic Potts model (2010) (84)
Learning linear transformations (1996) (74)
The Complexity of Ferromagnetic Ising with Local Fields (2006) (72)
Mathematical Foundations of the Markov Chain Monte Carlo Method (1998) (70)
The computational complexity of two‐state spin systems (2003) (68)
Bisimulation Equivanlence Is Decidable for Normed Process Algebra (1999) (66)
Random cluster dynamics for the Ising model is rapidly mixing (2016) (64)
Markov chain comparison (2004) (63)
A doubly logarithmic communication algorithm for the completely connected optical communication parallel computer (1993) (62)
Uniform sampling through the Lovasz local lemma (2017) (62)
Generating and Counting Hamilton Cycles in Random Regular Graphs (1996) (60)
An approximation trichotomy for Boolean #CSP (2007) (59)
A mildly exponential approximation algorithm for the permanent (1992) (55)
On Approximately Counting Colorings of Small Degree Graphs (1999) (53)
#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region (2013) (49)
Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows (2002) (46)
On continuous Homotopic one layer routing (1988) (45)
The complexity of weighted and unweighted #CSP (2010) (43)
A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language (1997) (42)
An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings (2001) (41)
Two-dimensional monomer-dimer systems are computationally intractable (1987) (40)
The expressibility of functions on the boolean domain, with applications to counting CSPs (2011) (40)
Dobrushin Conditions and Systematic Scan (2006) (39)
A bound on the capacity of backoff and acknowledgment-based protocols (2004) (39)
Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers (1997) (37)
Matrix norms and rapid mixing for spin systems (2007) (36)
An analysis of a Monte Carlo algorithm for estimating the permanent (1995) (36)
The parameterised complexity of counting connected subgraphs and graph motifs (2013) (35)
Approximately Counting Hamilton Paths and Cycles in Dense Graphs (1998) (34)
Systematic scan for sampling colorings (2006) (33)
Spectral gap and log-Sobolev constant for balanced matroids (2002) (33)
A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability (2017) (31)
Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version) (1988) (30)
On the Switch Markov Chain for Perfect Matchings (2015) (29)
The Complexity of Computing the Sign of the Tutte Polynomial (2012) (29)
Polynomial-Time Approximation Algorithms for Ising Model (Extended Abstract) (1990) (29)
Approximately counting Hamilton cycles in dense graphs (1994) (27)
On the complexity of evaluating multivariate polynomials (1981) (26)
The Swendsen–Wang Process Does Not Always Mix Rapidly (1999) (26)
A polynomial-time algorithm for deciding equivalence of normed context-free processes (1994) (24)
The complexity of approximating conservative counting CSPs (2012) (24)
An Ω(√ log log n) lower bound for routing in optical networks (1994) (23)
Two Remarks Concerning Balanced Matroids (2004) (23)
Convergence of the Iterated Prisoner's Dilemma Game (2002) (23)
Counting and sampling H-colourings? (2004) (23)
Perfect simulation of the Hard Disks Model by Partial Rejection Sampling (2018) (22)
A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols (2000) (22)
Inapproximability of the Tutte polynomial of a planar graph (2009) (22)
Uniform Sampling Through the Lovász Local Lemma (2016) (22)
Random Generation of Combinatorial Structures from a Uniform Distribution (Extended Abstract) (1985) (21)
Families of Fixed Degree Graphs for Processor Interconnection (1984) (21)
An elementary analysis of a procedure for sampling points in a convex body (1998) (19)
Approximately counting bases of bicircular matroids (2018) (18)
COUNTING UNLABELLED SUBTREES OF A TREE IS #P-COMPLETE (2000) (18)
Uniform Sampling Modulo a Group of Symmetries Using Markov Chain Simulation (1992) (17)
The mixing time of Glauber dynamics for coloring regular trees (2008) (17)
The Complexity of Parity Graph Homomorphism: An Initial Investigation (2013) (16)
Some Hard Families of Parameterized Counting Problems (2013) (16)
Randomly sampling molecules (1997) (16)
Approximately Counting H-Colourings is #BIS-Hard (2015) (15)
The parameterised complexity of counting even and odd induced subgraphs (2014) (15)
The Computational Complexity of Counting (1995) (15)
Approximately Counting H-Colorings is $\#\mathrm{BIS}$-Hard (2015) (15)
A complexity classification of spin systems with an external field (2015) (15)
Counting Trees in a Graph is #P-Complete (1994) (14)
A Complexity Dichotomy For Hypergraph Partition Functions (2008) (13)
A Complexity Trichotomy for Approximately Counting List H-Colorings (2016) (12)
Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs (2002) (12)
A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid (2010) (11)
Perfect Sampling in Infinite Spin Systems via Strong Spatial Mixing (2021) (11)
The Complexity of Finding Minimum-Length Generator Sequences (Extended Abstract) (1984) (10)
A Counterexample to rapid mixing of the Ge-Stefankovic Process (2011) (10)
The Complexity of Approximately Counting Tree Homomorphisms (2013) (10)
Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials (2010) (9)
Bounding the Vapnik-Chervonenkis dimension of concept classes parameterized by real numbers (2004) (8)
On the approximation of one Markov chain by another (2003) (8)
Simple Translation-Invariant Concepts Are Hard to Learn (1994) (8)
Log-supermodular functions, functional clones and counting CSPs (2011) (8)
The Complexity of Computing the Sign of the Tutte Polynomial (and Consequent #P-hardness of Approximation) (2012) (7)
The "Burnside Process" Converges Slowly (1998) (6)
Approximating the partition function of planar two-state spin systems (2012) (6)
Fundamentals of Partial Rejection Sampling (2021) (5)
Counting and Sampling H-Colourings (2002) (5)
Surveys in Combinatorics, 1995: Computational Pólya theory (1995) (5)
A New Approach to Polynomial-Time Generation of Random Points in Convex Bodies (1996) (5)
An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract) (2000) (5)
Approximating Pairwise Correlations in the Ising Model (2018) (5)
Random Walks on Small World Networks (2017) (4)
A lower bound for routing on a completely connected optical communication parallel computer (1993) (4)
APPROXIMATING THE TUTTE POLYNOMIAL (2007) (4)
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs (2020) (4)
An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks (1998) (4)
The Parameterised Complexity of Counting Connected Subgraphs (2013) (4)
Functional clones and expressibility of partition functions (2016) (4)
The ‘Burnside Process’ Converges Slowly (2002) (4)
Constraint satisfaction problems and computational complexity (2010) (3)
Counting weighted independent sets beyond the permanent (2019) (3)
Two good counting algorithms (2003) (2)
The complexity of counting locally maximal satisfying assignments of Boolean CSPs (2015) (2)
Counting Constraint Satisfaction Problems. (2017) (2)
Sampling and counting (2003) (2)
Volume of a convex body (2003) (2)
A simple FPRAS for bi-directed reachability (2017) (2)
Computational Po´lya theory (1995) (1)
Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs (2013) (1)
Some hard classes of parameterised counting problems (2013) (1)
Perfect Sampling of q-Spin Systems on ℤ2 via Weak Spatial Mixing (2023) (1)
On Continuous Homotopic One Layer Routing (Extended Abstract) (1988) (1)
Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard (2015) (0)
10481 Abstracts Collection - Computational Counting (2010) (0)
08201 – Abstract Collection Design and Analysis of Randomized and Approximation Algorithms — Dagstuhl Seminar — (2008) (0)
Perfect Sampling of $q$-Spin Systems on $\mathbb Z^2$ via Weak Spatial Mixing (2023) (0)
Counting vertices of integer polytopes defined by facets (2021) (0)
A pr 2 01 9 Approximating Pairwise Correlations in the Ising Model ∗ (2019) (0)
Preface (1988) (0)
Ja n 20 19 UNIFORM SAMPLING THROUGH THE LOVÁSZ LOCAL LEMMA (2021) (0)
D M ] 2 8 A pr 2 01 7 Functional Clones and Expressibility of Partition Functions ∗ (2018) (0)
Computational Counting (Dagstuhl Seminar 13031) (2013) (0)
Technical Perspective Constraint Satisfaction Problems and Computational Complexity (2010) (0)
4 Concluding Remarks Acknowledgements (1994) (0)
Counting Constraint Satisfaction Problems (2017) (0)
CPC volume 4 issue 4 Cover and Front matter (1995) (0)
CPC volume 4 issue 1 Cover and Front matter (1995) (0)
Spin systems with an external ﬁeld: a complexity classiﬁcation (2015) (0)
CPC volume 3 issue 4 Cover and Front matter (1994) (0)
Themes Complexity Theory ’ 94 In the months of August and September , 1994 (0)
Review: E. G. Coffman, George S. Lueker, Probabilistic Analysis of Packing and Partitioning Algorithms (1992) (0)
10481 Executive Summary - Computational Counting (2010) (0)
An extension of path oupling and its appli ation tothe (2006) (0)
Inapproximability of the Tutte polynomial of a planar graph (2012) (0)
The size of the joint-giant component in a binomial random double graph. (2019) (0)
The parameterised complexity of counting even and odd induced subgraphs (2016) (0)
A simple polynomial-time approximation algorithm for the total variation distance between two product distributions (2022) (0)
The Mixing Rate of Glauber Dynamics for Sampling Colourings of Regular Trees with Few Colours (2011) (0)
Computational Counting (Dagstuhl Seminar 18341) (2017) (0)
CPC volume 4 issue 3 Cover and Front matter (1995) (0)
Timed Modal Specifications........ 8 (0)
05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms (2005) (0)
The expressibility of Boolean functions with applications to Counting CSPs (2011) (0)
A simple polynomial-time approximation algorithm for total variation distances between product distributions (2022) (0)
The complexity of Boolean #MaximalCSP (2015) (0)
The Mixing Time of Glauber Dynamics for Colouring Regular Trees (Revised Version) (2011) (0)
CPC volume 3 issue 1 Cover and Front matter (1994) (0)
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 01231) (2021) (0)
CPC volume 2 issue 3 Cover and Front matter (1993) (0)
CPC volume 4 issue 2 Cover and Front matter (1995) (0)
CPC volume 2 issue 4 Cover and Front matter (1993) (0)
CPC volume 3 issue 3 Cover and Front matter (1994) (0)
Edinburgh Research Explorer Uniform sampling through the Lovasz local lemma (2017) (0)
Canonical paths and matchings (2003) (0)
CPC volume 5 issue 2 Cover and Front matter (1996) (0)
A COMPLEXITY DICHOTOMY FOR PARTITION FUNCTIONS WITH (2009) (0)
Coupling and colourings (2003) (0)
CPC volume 1 issue 3 Cover and Front matter (1992) (0)
CPC volume 1 issue 2 Cover and Front matter (1992) (0)
The Size of the Giant Joint Component in a Binomial Random Double Graph (2021) (0)
CPC volume 2 issue 1 Cover and Front matter (1993) (0)
CPC volume 2 issue 2 Cover and Front matter (1993) (0)

This paper list is powered by the following services:

Other Resources About Mark Jerrum

en.wikipedia.org

What Schools Are Affiliated With Mark Jerrum?

Mark Jerrum is affiliated with the following schools:

Mark Jerrum's Academic­Influence.com Rankings

Why Is Mark Jerrum Influential?

Mark Jerrum's Published Works

Published Works

Other Resources About Mark Jerrum

What Schools Are Affiliated With Mark Jerrum?

Mark Jerrum's AcademicInfluence.com Rankings