Publications

# Publications :: Search

## Show author

On this page you see the details of the selected author.

 Author information First name: Mark Last name: Jerrum DBLP: j/MarkJerrum Rating: (not rated yet) Bookmark:

Below you find the publications which have been written by this author.

Show item 1 to 100 of 155
 Select a publication Show Title Venue Rating Date Conference paper Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo 0001, 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. 2016, Volume 82 (0) 2016 Conference paper 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. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2014, September 4-6, 2014, Barcelona, Spain 2014 (0) 2014 Conference paper Martin E. Dyer, Mark Jerrum, Marek Karpinski. 05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. Design and Analysis of Randomized and Approximation Algorithms, 15.05. - 20.05.2005 2005 (0) 2005 Conference paper 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, 11.05. - 16.05.2008 2008 (0) 2008 Conference paper Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum. 10481 Abstracts Collection - Computational Counting. Computational Counting, 28.11. - 03.12.2010 2010 (0) 2010 Conference paper Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum. 10481 Executive Summary - Computational Counting. Computational Counting, 28.11. - 03.12.2010 2010 (0) 2010 Conference paper Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson. A Bound on the Capacity of Backoff and Acknowledgement-Based Protocols. Automata, Languages and Programming, 27th International Colloquium, ICALP 2000, Geneva, Switzerland, July 9-15, 2000, Proceedings 2000 (0) 2000 Conference paper Leslie Ann Goldberg, Mark Jerrum, Sampath Kannan, Mike Paterson. A bound on the capacity of backoff and acknowledgment-based protocols. SIAM J. Comput. 2004, Volume 33 (0) 2004 Conference paper Mark Jerrum. A Compact Representation for Permutation Groups 23rd Annual Symposium on Foundations of Computer Science, Chicago, Illinois, USA, 3-5 November 1982 1982 (0) 1982 Conference paper Mark Jerrum. A Compact Representation for Permutation Groups. J. Algorithms 1986, Volume 7 (0) 1986 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. A complexity dichotomy for hypergraph partition functions CoRR 2008, Volume 0 (0) 2008 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. A Complexity Dichotomy For Hypergraph Partition Functions. Computational Complexity 2010, Volume 19 (0) 2010 Conference paper Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley. A complexity dichotomy for partition functions with mixed signs CoRR 2008, Volume 0 (0) 2008 Conference paper Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley. A Complexity Dichotomy for Partition Functions with Mixed Signs. SIAM J. Comput. 2009, Volume 39 (0) 2010 Conference paper Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley. A Complexity Dichotomy for Partition Functions with Mixed Signs. 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26-28, 2009, Freiburg, Germany, Proceedings 2009 (0) 2009 Conference paper Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. A Complexity Trichotomy for Approximately Counting List TOCT 2016, Volume 9 (0) 2017 Journal article Leslie Ann Goldberg, Mark Jerrum. A complexity trichotomy for approximately counting list H-colourings. CoRR 2016, Volume 0 (0) 2016 Conference paper Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. A Complexity Trichotomy for Approximately Counting List H-Colourings. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy 2016 (0) 2016 Journal article Leslie Ann Goldberg, Mark Jerrum. A Counterexample to rapid mixing of the Ge-Stefankovic Process CoRR 2011, Volume 0 (0) 2011 Conference paper Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao. A Doubly Logarithmic Communication Algorithm for the Completely Connected Optical Communication Parallel Computer. SPAA 1993 (0) 1993 Conference paper Mark Jerrum, Umesh V. Vazirani. A Mildly Exponential Approximation Algorithm for the Permanent 33rd Annual Symposium on Foundations of Computer Science, Pittsburgh, Pennsylvania, USA, 24-27 October 1992 1992 (0) 1992 Conference paper Mark Jerrum, Umesh V. Vazirani. A Mildly Exponential Approximation Algorithm for the Permanent. Algorithmica 1996, Volume 16 (0) 1996 Conference paper Yoram Hirshfeld, Mark Jerrum, Faron Moller. A Polynomial Algorithm for Deciding Bisimilarity of Normed Context-Free Processes. Theor. Comput. Sci. 1996, Volume 158 (0) 1996 Conference paper Yoram Hirshfeld, Mark Jerrum, Faron Moller. A Polynomial-Time Algorithm for Deciding Bisimulation Equivalence of Normed Basic Parallel Processes. Mathematical Structures in Computer Science 1996, Volume 6 (0) 1996 Conference paper Yoram Hirshfeld, Mark Jerrum, Faron Moller. A Polynomial-time Algorithm for Deciding Equivalence of Normed Context-free Processes 35th Annual Symposium on Foundations of Computer Science, Santa Fe, New Mexico, USA, 20-22 November 1994 1994 (0) 1994 Journal article 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, Volume 0 (0) 2010 Conference paper 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. 2013, Volume 42 (0) 2013 Conference paper Leslie Ann Goldberg, Mark Jerrum. A Polynomial-Time Algorithm for Estimating the Partition Function of the Ferromagnetic Ising Model on a Regular Matroid. Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I 2011 (0) 2011 Conference paper Mark Jerrum, Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries Electronic Colloquium on Computational Complexity (ECCC) 2000, Volume 7 (0) 2000 Conference paper Mark Jerrum, Alistair Sinclair, Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. STOC 2001 (0) 2001 Conference paper Mark Jerrum, Alistair Sinclair, Eric Vigoda. A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries. J. ACM 2004, Volume 51 (0) 2004 Conference paper Vivek Gore, Mark Jerrum, Sampath Kannan, Z. Sweedyk, Stephen R. Mahaney. A Quasi-Polynomial-Time Algorithm for Sampling Words from a Context-Free Language. Inf. Comput. 1997, Volume 134 (0) 1997 Journal article Heng Guo 0001, Mark Jerrum. A simple FPRAS for bi-directed reachability. CoRR 2017, Volume 0 (0) 2017 Conference paper Mark Jerrum. A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph. Random Struct. Algorithms 1995, Volume 7 (0) 1995 Conference paper Alan M. Frieze, Mark Jerrum. An Analysis of a Monte Carlo Algorithm for Estimating the Permanent. Combinatorica 1995, Volume 15 (0) 1995 Conference paper Mark Jerrum. An analysis of a Monte Carlo algorithm for estimating the permanent. Proceedings of the 3rd Integer Programming and Combinatorial Optimization Conference, Erice, Italy, April 29 - May 1, 1993 1993 (0) 1993 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. An approximation trichotomy for Boolean #CSP CoRR 2007, Volume 0 (0) 2007 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. An approximation trichotomy for Boolean #CSP. J. Comput. Syst. Sci. 2010, Volume 76 (0) 2010 Conference paper Russ Bubley, Martin E. Dyer, Mark Jerrum. An elementary analysis of a procedure for sampling points in a convex body. Random Struct. Algorithms 1998, Volume 12 (0) 1998 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher. An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings. SIAM J. Comput. 2000, Volume 30 (0) 2000 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher. An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). SODA 2000 (0) 2000 Conference paper Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie. An Omega(sqrt{log log n}) Lower Bound for Routing in Optical Networks. SIAM J. Comput. 1998, Volume 27 (0) 1998 Conference paper Leslie Ann Goldberg, Mark Jerrum, Philip D. MacKenzie. An W(log log n) Lower Bound for Routing in Optical Networks. SPAA 1994 (0) 1994 Conference paper Alistair Sinclair, Mark Jerrum. Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains Inf. Comput. 1989, Volume 82 (0) 1989 Conference paper Alistair Sinclair, Mark Jerrum. Approximate Counting, Uniform Generation and Rapidly Mixing Markov Chains. Graph-Theoretic Concepts in Computer Science, International Workshop, WG '87, Kloster Banz/Staffelstein, Germany, June 29 - July 1, 1987, Proceedings 1988 (0) 1987 Conference paper Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. Approximately Counting H-Colorings is $\#\mathrm{BIS}$-Hard. SIAM J. Comput. 2016, Volume 45 (0) 2016 Journal article Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. Approximately Counting H-Colourings is #BIS-Hard. CoRR 2015, Volume 0 (0) 2015 Conference paper Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum. Approximately Counting H-Colourings is #\mathrm BIS # BIS -Hard. Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part I 2015 (0) 2015 Conference paper Martin E. Dyer, Alan M. Frieze, Mark Jerrum. Approximately Counting Hamilton Cycles in Dense Graphs. SODA 1994 (0) 1994 Conference paper Martin E. Dyer, Alan M. Frieze, Mark Jerrum. Approximately Counting Hamilton Paths and Cycles in Dense Graphs. SIAM J. Comput. 1998, Volume 27 (0) 1998 Conference paper Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan. Approximating the partition function of planar two-state spin systems CoRR 2012, Volume 0 (0) 2012 Journal article Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan. Approximating the partition function of planar two-state spin systems. J. Comput. Syst. Sci. 2015, Volume 81 (0) 2015 Journal article Leslie Ann Goldberg, Mark Jerrum. Approximating the partition function of the ferromagnetic Potts model CoRR 2010, Volume 0 (0) 2010 Conference paper Leslie Ann Goldberg, Mark Jerrum. Approximating the partition function of the ferromagnetic potts model. J. ACM 2012, Volume 59 (0) 2012 Conference paper Leslie Ann Goldberg, Mark Jerrum. Approximating the Partition Function of the Ferromagnetic Potts Model. Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I 2010 (0) 2010 Journal article Jin-Yi Cai, Leslie Ann Goldberg, Heng Guo, Mark Jerrum. Approximating the Partition Function of Two-Spin Systems on Bipartite Graphs. CoRR 2013, Volume 0 (0) 2013 Conference paper Mark Jerrum, Alistair Sinclair. Approximating the Permanent. SIAM J. Comput. 1989, Volume 18 (0) 1989 Journal article Leslie Ann Goldberg, Mark Jerrum. Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials CoRR 2010, Volume 0 (0) 2010 Journal article Leslie Ann Goldberg, Mark Jerrum. Approximating the Tutte polynomial of a binary matroid and other related combinatorial polynomials. J. Comput. Syst. Sci. 2013, Volume 79 (0) 2013 Conference paper Yoram Hirshfeld, Mark Jerrum. Bisimulation Equivanlence Is Decidable for Normed Process Algebra. Automata, Languages and Programming, 26th International Colloquium, ICALP'99, Prague, Czech Republic, July 11-15, 1999, Proceedings 1999 (0) 1999 Conference paper Paul W. Goldberg, Mark Jerrum. Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. Machine Learning 1995, Volume 18 (0) 1995 Conference paper Paul W. Goldberg, Mark Jerrum. Bounding the Vapnik-Chervonenkis Dimension of Concept Classes Parameterized by Real Numbers. COLT 1993 (0) 1993 Journal article Peter Bürgisser, Leslie Ann Goldberg, Mark Jerrum, Pascal Koiran. Computational Counting (Dagstuhl Seminar 13031). Dagstuhl Reports 2013, Volume 3 (0) 2013 Conference paper Mark Jerrum, Alistair Sinclair. Conductance and the Rapid Mixing Property for Markov Chains: the Approximation of the Permanent Resolved (Preliminary Version) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2-4, 1988, Chicago, Illinois, USA 1988 (0) 1988 Conference paper Mark Jerrum. Constraint satisfaction problems and computational complexity: technical persepctive. Commun. CACM 2010, Volume 53 (0) 2010 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Gabriel Istrate, Mark Jerrum. Convergence Of The Iterated Prisoner's Dilemma Game Combinatorics, Probability Computing 2002, Volume 11 (0) 2002 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Counting and Sampling H-Colourings. Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings 2002 (0) 2002 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Counting and sampling H-colourings? Inf. Comput. 2004, Volume 189 (0) 2004 Book chapter Mark Jerrum. Counting Constraint Satisfaction Problems. The Constraint Satisfaction Problem: Complexity and Approximability 2017, Volume 7 (0) 2017 Conference paper Mark Jerrum. Counting Trees in a Graph is #P-Complete. Inf. Process. Lett. 1994, Volume 51 (0) 1994 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Dobrushin conditions and Systematic Scan Electronic Colloquium on Computational Complexity (ECCC) 2005, Volume null (0) 2005 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Dobrushin Conditions and Systematic Scan. Combinatorics, Probability Computing 2008, Volume 17 (0) 2008 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Dobrushin Conditions and Systematic Scan. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 9th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2006 and 10th International Workshop on Randomization and Compu 2006 (0) 2006 Conference paper Leslie Ann Goldberg, Mark Jerrum, Frank Thomson Leighton, Satish Rao. Doubly Logarithmic Communication Algorithms for Optical-Communication Parallel Computers. SIAM J. Comput. 1997, Volume 26 (0) 1997 Conference paper Mark Jerrum, Sven Skyum. Families of Fixed Degree Graphs for Processor Interconnection. IEEE Trans. Computers 1984, Volume 33 (0) 1984 Conference paper Mark Jerrum, Alistair Sinclair. Fast Uniform Generation of Regular Graphs. Theor. Comput. Sci. 1990, Volume 73 (0) 1990 Journal article Andrei A. Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivny. Functional clones and expressibility of partition functions. Theor. Comput. Sci. 2017, Volume 687 (0) 2017 Conference paper Andrei A. Bulatov, Leslie Ann Goldberg, Mark Jerrum, David Richerby, Stanislav Zivny. Functional Clones and Expressibility of Partition Functions. CoRR 2016, Volume 0 (0) 2016 Conference paper Alan M. Frieze, Mark Jerrum, Michael Molloy, Robert W. Robinson, Nicholas C. Wormald. Generating and Counting Hamilton Cycles in Random Regular Graphs. J. Algorithms 1996, Volume 21 (0) 1996 Conference paper Alan M. Frieze, Mark Jerrum. Improved Approximation Algorithms for MAX Integer Programming and Combinatorial Optimization, 4th International IPCO Conference, Copenhagen, Denmark, May 29-31, 1995, Proceedings 1995 (0) 1995 Conference paper Alan M. Frieze, Mark Jerrum. Improved Approximation Algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 1997, Volume 18 (0) 1997 Conference paper Leslie Ann Goldberg, Mark Jerrum. Inapproximability of the Tutte polynomial CoRR 2006, Volume 0 (0) 2006 Conference paper Leslie Ann Goldberg, Mark Jerrum. Inapproximability of the Tutte polynomial of a planar graph CoRR 2009, Volume 0 (0) 2009 Conference paper Leslie Ann Goldberg, Mark Jerrum. Inapproximability of the Tutte polynomial of a planar graph. Computational Complexity 2012, Volume 21 (0) 2012 Conference paper Leslie Ann Goldberg, Mark Jerrum. Inapproximability of the Tutte polynomial. Inf. Comput. 2008, Volume 206 (0) 2008 Conference paper Leslie Ann Goldberg, Mark Jerrum. Inapproximability of the Tutte polynomial. Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007 2007 (0) 2007 Conference paper Mark Jerrum. Large Cliques Elude the Metropolis Process. Random Struct. Algorithms 1992, Volume 3 (0) 1992 Conference paper Alan M. Frieze, Mark Jerrum, Ravi Kannan. Learning Linear Transformations. FOCS 1996 (0) 1996 Journal article Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Log-supermodular functions, functional clones and counting CSPs CoRR 2011, Volume 0 (0) 2011 Conference paper Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Log-supermodular functions, functional clones and counting CSPs. 29th International Symposium on Theoretical Aspects of Computer Science, STACS 2012, February 29th - March 3rd, 2012, Paris, France 2012 (0) 2012 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Matrix norms and rapid mixing for spin systems CoRR 2007, Volume 0 (0) 2007 Conference paper Russ Bubley, Martin E. Dyer, Catherine S. Greenhill, Mark Jerrum. On Approximately Counting Colorings of Small Degree Graphs. SIAM J. Comput. 2000, Volume 29 (0) 1999 Conference paper Shaodi Gao, Michael Kaufmann, Kurt Mehlhorn, Wolfgang Rülling, Christoph Storb, Mark Jerrum. On Continuous Homotopic One Layer Routing. Computational Geometry and its Applications, CG'88, International Workshop on Computational Geometry, Würzburg, Germany, March 24-25, 1988 1988 (0) 1988 Conference paper Shaodi Gao, Mark Jerrum, Michael Kaufmann, Kurt Mehlhorn, Wolfgang Rülling. On Continuous Homotopic One Layer Routing. Symposium on Computational Geometry 1988 (0) 1988 Conference paper Martin E. Dyer, Alan M. Frieze, Mark Jerrum. On Counting Independent Sets in Sparse Graphs. SIAM J. Comput. 2001, Volume 31 (0) 2002 Conference paper Martin E. Dyer, Alan M. Frieze, Mark Jerrum. On Counting Independent Sets in Sparse Graphs. FOCS 1999 (0) 1999 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum. On the relative complexity of approximate counting problems. Approximation Algorithms for Combinatorial Optimization, Third International Workshop, APPROX 2000, Saarbrücken, Germany, September 5-8, 2000, Proceedings 2000 (0) 2000 Conference paper Martin E. Dyer, Mark Jerrum, Haiko Müller. On the Switch Markov Chain for Perfect Matchings. J. ACM 2017, Volume 64 (0) 2017 Conference paper Martin E. Dyer, Mark Jerrum, Haiko Müller. On the switch Markov chain for perfect matchings. Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016, Arlington, VA, USA, January 10-12, 2016 2016 (0) 2016 Journal article Martin E. Dyer, Mark Jerrum, Haiko Müller. On the switch Markov chain for perfect matchings. CoRR 2015, Volume 0 (0) 2015
Show item 1 to 100 of 155

Your query returned 155 matches in the database.