Publications

# Publications :: Search

## Show author

 Select a publication Show Title Venue Rating Date Conference paper Colin Cooper, Martin E. Dyer, Catherine S. Greenhill, Andrew J. Handley. The flip Markov chain for connected regular graphs. CoRR 2017, Volume 0 (0) 2017 Conference paper Martin E. Dyer, Haiko Müller. Counting perfect matchings and the switch chain. CoRR 2017, Volume 0 (0) 2017 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, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda. Random Walks on Small World Networks. CoRR 2017, Volume 0 (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 Conference paper Colin Cooper, Martin E. Dyer, Alan M. Frieze, Nicolas Rivera. Discordant voting processes on finite graphs. CoRR 2016, Volume 0 (0) 2016 Conference paper Colin Cooper, Martin E. Dyer, Alan M. Frieze, Nicolas Rivera. Discordant Voting Processes on Finite Graphs. 43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy 2016 (0) 2016 Conference paper Martin E. Dyer, Leslie Ann Goldberg, David Richerby. Counting 4×4 matrix partitions of graphs. Discrete Applied Mathematics 2016, Volume 213 (0) 2016 Journal article 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. 2015, Volume 81 (0) 2015 Journal article Martin E. Dyer, Mark Jerrum, Haiko Müller. On the switch Markov chain for perfect matchings. CoRR 2015, Volume 0 (0) 2015 Journal article Martin E. Dyer, Alan M. Frieze, Catherine S. Greenhill. On the chromatic number of a random hypergraph. J. Comb. Theory, Ser. B 2015, Volume 113 (0) 2015 Conference paper Martin E. Dyer, Leen Stougie. Erratum to: Computational complexity of stochastic programming problems. Math. Program. 2015, Volume 153 (0) 2015 Journal article Martin E. Dyer, Leslie Ann Goldberg, David Richerby. Counting $4\times 4$ Matrix Partitions of Graphs. CoRR 2014, Volume 0 (0) 2014 Conference paper Martin E. Dyer, R. Kannan, Leen Stougie. A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming. Math. Program. 2014, Volume 147 (0) 2014 Conference paper Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby. The complexity of approximating conservative counting CSPs. 30th International Symposium on Theoretical Aspects of Computer Science, STACS 2013, February 27 - March 2, 2013, Kiel, Germany 2013 (0) 2013 Conference paper Martin E. Dyer, David Richerby. An Effective Dichotomy for the Counting Constraint Satisfaction Problem. SIAM J. Comput. 2013, Volume 42 (0) 2013 Conference paper Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda. Randomly coloring constant degree graphs. Random Struct. Algorithms 2013, Volume 43 (0) 2013 Conference paper 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 2013, Volume 60 (0) 2013 Conference paper 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. 2012, Volume 78 (0) 2012 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, Alan M. Frieze, Catherine S. Greenhill. On the chromatic number of a random hypergraph CoRR 2012, Volume 0 (0) 2012 Conference paper 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, Volume 0 (0) 2012 Journal article Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby. The complexity of approximating bounded-degree Boolean #CSP. Inf. Comput. 2012, Volume 220 (0) 2012 Conference paper Martin E. Dyer, David Richerby. The #CSP Dichotomy is Decidable. 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France 2010 (0) 2011 Conference paper Colin Cooper, Martin E. Dyer, Andrew J. Handley. Networks of random cycles. Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2011, San Francisco, California, USA, January 23-25, 2011 2011 (0) 2011 Conference paper Martin E. Dyer, Velumailum Mohanaraj. Pairwise-Interaction Games. Automata, Languages and Programming - 38th International Colloquium, ICALP 2011, Zurich, Switzerland, July 4-8, 2011, Proceedings, Part I 2011 (0) 2011 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 Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski. Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). Dagstuhl Reports 2011, Volume 1 (0) 2011 Conference paper Mary Cryan, Martin E. Dyer, Dana Randall. Approximately Counting Integral Flows and Cell-Bounded Contingency Tables. SIAM J. Comput. 2009, Volume 39 (0) 2010 Journal article Andrei Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby. The complexity of weighted and unweighted #CSP CoRR 2010, Volume 0 (0) 2010 Conference paper Martin E. Dyer, David Richerby. On the complexity of #CSP. Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010 2010 (0) 2010 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. A Complexity Dichotomy For Hypergraph Partition Functions. Computational Complexity 2010, Volume 19 (0) 2010 Journal article Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby. The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract) CoRR 2010, Volume 0 (0) 2010 Conference paper Martin E. Dyer, Alan M. Frieze. Randomly coloring random graphs. Random Struct. Algorithms 2010, Volume 36 (0) 2010 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby. The Complexity of Approximating Bounded-Degree Boolean #CSP. 27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010, March 4-6, 2010, Nancy, France 2010 (0) 2010 Journal article Martin E. Dyer, David Richerby. The Complexity of #CSP CoRR 2010, Volume 0 (0) 2010 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 Colin Cooper, Martin E. Dyer, Andrew J. Handley. The flip markov chain and a randomising P2P protocol. Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, PODC 2009, Calgary, Alberta, Canada, August 10-12, 2009 2009 (0) 2009 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby. The Complexity of Approximating Bounded-Degree Boolean #CSP CoRR 2009, Volume 0 (0) 2009 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. The Complexity of Weighted Boolean CSP. SIAM J. Comput. 2008, Volume 38 (0) 2009 Conference paper Andrei Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby. The complexity of weighted Boolean #CSP with mixed signs. Theor. Comput. Sci. 2009, Volume 410 (0) 2009 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 Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. A complexity dichotomy for hypergraph partition functions CoRR 2008, Volume 0 (0) 2008 Conference paper Andrei Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby. The Complexity of Weighted Boolean #CSP with Mixed Signs CoRR 2008, Volume 0 (0) 2008 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 Magnus Bordewich, Martin E. Dyer, Marek Karpinski. Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Struct. Algorithms 2008, Volume 32 (0) 2008 Conference paper Mary Cryan, Martin E. Dyer, Haiko Müller, Leen Stougie. Random walks on the vertices of transportation polytopes with constant number of sources. Random Struct. Algorithms 2008, Volume 33 (0) 2008 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 Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. The Complexity of Weighted Boolean #CSP CoRR 2007, Volume 0 (0) 2007 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. An approximation trichotomy for Boolean #CSP CoRR 2007, Volume 0 (0) 2007 Conference paper Colin Cooper, Martin E. Dyer, Catherine S. Greenhill. Sampling Regular Graphs and a Peer-to-Peer Network. Combinatorics, Probability Computing 2007, Volume 16 (0) 2007 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson. On counting homomorphisms to directed acyclic graphs. J. ACM 2007, Volume 54 (0) 2007 Conference paper Magnus Bordewich, Martin E. Dyer. Path coupling without contraction. J. Discrete Algorithms 2007, Volume 5 (0) 2007 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 Magnus Bordewich, Martin E. Dyer, Marek Karpinski. Stopping Times, Metrics and Approximate Counting. Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I 2006 (0) 2006 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson. On Counting Homomorphisms to Directed Acyclic Graphs. Automata, Languages and Programming, 33rd International Colloquium, ICALP 2006, Venice, Italy, July 10-14, 2006, Proceedings, Part I 2006 (0) 2006 Conference paper Martin E. Dyer, Leen Stougie. Computational complexity of stochastic programming problems. Math. Program. 2006, Volume 106 (0) 2006 Conference paper Martin E. Dyer, Abraham D. Flaxman, Alan M. Frieze, Eric Vigoda. Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Struct. Algorithms 2006, Volume 29 (0) 2006 Conference paper Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell Martin. Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. SIAM J. Comput. 2006, Volume 36 (0) 2006 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 Magnus Bordewich, Martin E. Dyer, Marek Karpinski. Path Coupling Using Stopping Times. Fundamentals of Computation Theory, 15th International Symposium, FCT 2005, Lübeck, Germany, August 17-20, 2005, Proceedings 2005 (0) 2005 Conference paper Colin Cooper, Martin E. Dyer, Catherine S. Greenhill. Sampling regular graphs and a peer-to-peer network. Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2005, Vancouver, British Columbia, Canada, January 23-25, 2005 2005 (0) 2005 Conference paper Mary Cryan, Martin E. Dyer, Dana Randall. Approximately counting integral flows and cell-bounded contingency tables. Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005 2005 (0) 2005 Conference paper Magnus Bordewich, Martin E. Dyer, Marek Karpinski. Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs 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 Electronic Colloquium on Computational Complexity (ECCC) 2005, Volume null (0) 2005 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson. On counting homomorphisms to directed acyclic graphs Electronic Colloquium on Computational Complexity (ECCC) 2005, Volume null (0) 2005 Conference paper Magnus Bordewich, Martin E. Dyer, Marek Karpinski. Metric Construction, Stopping Times and Path Coupling. Electronic Colloquium on Computational Complexity (ECCC) 2005, Volume null (0) 2005 Conference paper Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda. Randomly Coloring Constant Degree Graphs. 45th Symposium on Foundations of Computer Science (FOCS 2004), 17-19 October 2004, Rome, Italy, Proceedings 2004 (0) 2004 Conference paper Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda. Randomly coloring constant degree graphs Electronic Colloquium on Computational Complexity (ECCC) 2004, Volume null (0) 2004 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum. Counting and sampling H-colourings? Inf. Comput. 2004, Volume 189 (0) 2004 Conference paper Martin E. Dyer, Catherine S. Greenhill. Corrigendum: The complexity of counting graph homomorphisms. Random Struct. Algorithms 2004, Volume 25 (0) 2004 Conference paper Martin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz. Mixing in time and space for lattice spin systems: A combinatorial view. Random Struct. Algorithms 2004, Volume 24 (0) 2004 Conference paper Sammani D. Abdullahi, Martin E. Dyer, Les G. Proll. Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems. Discrete Mathematics and Theoretical Computer Science, 4th International Conference, DMTCS 2003, Dijon, France, July 7-12, 2003. Proceedings 2003 (0) 2003 Conference paper Mary Cryan, Martin E. Dyer, Haiko Müller, Leen Stougie. Random walks on the vertices of transportation polytopes with constant number of sources. SODA 2003 (0) 2003 Conference paper Martin E. Dyer. Approximate counting by dynamic programming. Proceedings of the 35th Annual ACM Symposium on Theory of Computing, June 9-11, 2003, San Diego, CA, USA 2003 (0) 2003 Conference paper Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum. The Relative Complexity of Approximate Counting Problems. Algorithmica 2003, Volume 38 (0) 2003 Conference paper Mary Cryan, Martin E. Dyer. A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. J. Comput. Syst. Sci. 2003, Volume 67 (0) 2003 Conference paper Martin E. Dyer, Alan M. Frieze. Randomly coloring graphs with lower bounds on girth and maximum degree. Random Struct. Algorithms 2003, Volume 23 (0) 2003 Conference paper Martin E. Dyer, Alan M. Frieze, Michael Molloy. A probabilistic analysis of randomly generated binary constraint satisfaction problems. Theor. Comput. Sci. 2003, Volume 290 (0) 2003 Conference paper Mary Cryan, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Russell Martin. Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. 43rd Symposium on Foundations of Computer Science (FOCS 2002), 16-19 November 2002, Vancouver, BC, Canada, Proceedings 2002 (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, Mark Jerrum, Eric Vigoda. Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. 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, Alistair Sinclair, Eric Vigoda, Dror Weitz. Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View. Randomization and Approximation Techniques, 6th International Workshop, RANDOM 2002, Cambridge, MA, USA, September 13-15, 2002, Proceedings 2002 (0) 2002 Conference paper Mary Cryan, Martin E. Dyer. A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. STOC 2002 (0) 2002 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, Catherine S. Greenhill, Michael Molloy. Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs. Random Struct. Algorithms 2002, Volume 20 (0) 2002 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 Christian Borgs, Jennifer T. Chayes, Martin E. Dyer, Prasad Tetali. On the Sampling Problem for H-Colorings on the Hypercubic Lattice. Graphs, Morphisms and Statistical Physics, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, March 19-21, 2001 2004 (0) 2001 Conference paper Martin E. Dyer, Mark Jerrum, Eric Vigoda. Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. Graphs, Morphisms and Statistical Physics, Proceedings of a DIMACS Workshop, New Brunswick, New Jersey, USA, March 19-21, 2001 2004 (0) 2001 Conference paper Martin E. Dyer, Alan M. Frieze. Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree. FOCS 2001 (0) 2001 Conference paper Colin Cooper, Martin E. Dyer, Alan M. Frieze. On Markov Chains for Randomly H-Coloring a Graph. J. Algorithms 2001, Volume 39 (0) 2001 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, Catherine S. Greenhill. The complexity of counting graph homomorphisms (extended abstract). SODA 2000 (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 Martin E. Dyer, Catherine S. Greenhill. On Markov Chains for Independent Sets. J. Algorithms 2000, Volume 35 (0) 2000 Conference paper Martin E. Dyer, Catherine S. Greenhill. The complexity of counting graph homomorphisms. Random Struct. Algorithms 2000, Volume 17 (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 Colorings. SIAM J. Comput. 2000, Volume 30 (0) 2000 Conference paper Martin E. Dyer, Sandeep Sen. Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems. SIAM J. Comput. 2000, Volume 30 (0) 2000 Conference paper Martin E. Dyer, Catherine S. Greenhill. Polynomial-time counting and sampling of two-rowed contingency tables. Theor. Comput. Sci. 2000, Volume 246 (0) 2000 Conference paper Martin E. Dyer, Alan M. Frieze, Mark Jerrum. On Counting Independent Sets in Sparse Graphs. FOCS 1999 (0) 1999