[]

Martin Dyer

Publications

Refereed Publications (2000-2015)

  • "Counting 4 x 4 matrix partitions of graphs"
    Martin Dyer, Leslie Ann Goldberg and David Richerby
    Discrete Applied Mathematics 213, 76-92, 2016.

  • "On the switch Markov chain for perfect matchings"
    Martin Dyer, Mark Jerrum and Haiko Müller
    Journal of the ACM, to appear.
    A preliminary version appeared in
    Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
    ACM/SIAM Press, pp. 1972-1983, 2016.

  • "Graph classes and the switch Markov chain for matchings "
    Martin Dyer and Haiko Müller
    Annales de la Faculté des Sciences de Toulouse XXIV, 885-993, 2015..

  • "On the chromatic number of a random hypergraph"
    Martin Dyer, Alan Frieze and Catherine Greenhill
    Journal of Combinatorial Theory, Series B, 113 C, 68-122, 2015.

  • "The complexity of approximating conservative counting CSPs"
    Xi Chen, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan and David Richerby
    Journal of Computer and Systems Sciences 81, 311-329, 2015.
    A preliminary version appeared in
    Proc. 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)
    Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 148-159, 2013.

  • "A simple randomised algorithm for convex optimisation–application to two-stage stochastic programming"
    Martin Dyer, Ravi Kannan and Leen Stougie
    Mathematical Programming 147, 207-229, 2014.

  • "Structure and eigenvalues of heat-bath Markov chains"
    Martin Dyer, Catherine Greenhill and Mario Ullrich
    Linear Algebra and its Applications 454, 57-71, 2014.

  • "The expressibility of functions on the Boolean domain, with applications to counting CSPs"
    Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and Colin McQuillan
    Journal of the ACM 60, Article 32, 2013.

  • "An effective dichotomy for the counting constraint satisfaction problem"
    Martin Dyer and David Richerby
    SIAM Journal on Computing 42, 1245-1274, 2013.
    A preliminary version appeared as
    "On the complexity of #CSP"
    Proc. 42nd ACM Symposium on Theory of Computing (STOC 2010)
    ACM Press, pp. 725-734, 2010.

  • "Randomly coloring constant degree graphs"
    Martin Dyer, Alan Frieze, Thomas Hayes and Eric Vigoda
    Random Structures and Algorithms 43, 181-200, 2013.
    A preliminary version appeared in
    Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 04),
    IEEE Computer Society Press, pp. 582-589, 2004.

  • "The complexity of approximating bounded-degree Boolean #CSP"
    Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius and David Richerby
    Information and Computation  220-221, 1-14, 2012.
    A preliminary version appeared in
    Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010),
    Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 323-334, 2010.

  • "Log-supermodular functions, functional clones and counting CSPs"
    Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
    in Proc. 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
    Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 302-313, 2012.

  • "The complexity of weighted and unweighted #CSP"
    Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum and David Richerby
    Journal of Computer and System Sciences 78, 681-688, 2012.

  • "Pairwise-interaction games"
    Martin Dyer and Velumailum Mohanaraj
    in Proc. Automata, Languages and Programming – 38th International Colloquium (ICALP 2011), Vol. 1
    Lecture Notes in Computer Science 6755, Springer, pp. 159-170, 2011.

  • "Networks of random cycles"
    Colin Cooper, Martin Dyer, and Andrew Handley
    in Proc. 22nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2011)
    ACM/SIAM Press, pp. 933-944, 2011.

  • "The #CSP dichotomy is decidable"
    Martin Dyer and David Richerby
    in Proc. 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
    Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 261-272, 2011.

  • "A complexity dichotomy for hypergraph partition functions"
    Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
    Computational Complexity 19, 605-633, 2010.

  • "Approximately counting integral flows and cell-bounded contingency tables"
    Mary Cryan, Martin Dyer and Dana Randall
    SIAM Journal on Computing 30, 2683-2703, 2010.
    A preliminary version appeared in
    Proc. 37th Annual ACM Symposium on the Theory of Computing (STOC 2005),
    ACM Press, pp. 413-422, 2005.

  • "An approximation trichotomy for Boolean #CSP"
    Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
    Journal of Computer and System Sciences 76, 267-277, 2010.

  • "Randomly coloring random graphs"
    Martin Dyer and Alan Frieze
    Random Structures and Algorithms 36, 251-272, 2010.

  • "Matrix norms and rapid mixing of spin systems"
    Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
    The Annals of Applied Probability 19, 71-107, 2009.

  • "The flip Markov chain and a randomising P2P protocol"
    Colin Cooper, Martin Dyer and Andrew Handley
    in Proc. 28th Annual ACM Symposium on Principles of Distributed Computing (PODC 09),
    ACM Press, pp. 141-150, 2009.

  • "The complexity of weighted Boolean #CSP"
    Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
    SIAM Journal on Computing 38, 1970-1986, 2009.

  • "The complexity of weighted Boolean #CSP with mixed signs"
    Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius and David Richerby
    Theoretical Computer Science 410, 3949-3961, 2009.

  • "Dobrushin conditions and systematic scan"
    Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
    Combinatorics, Probability and Computing 17, 761-779, 2008.
    A preliminary version appeared in
    Proc. 10th International Workshop on Randomization and Computation (RANDOM 06),
    Lecture Notes in Computer Science 4110, Springer, pp. 327-338, 2006.

  • "Path coupling using stopping times and counting independent sets and colorings in hypergraphs"
    Magnus Bordewich, Martin Dyer and Marek Karpinski
    Random Structures and Algorithms 32, 375-399, 2008.
    A preliminary version appeared as
    "Path coupling using stopping times"
    in Proc. 15th Annual Symposium on Fundamentals of Computation Theory (FCT 05),
    Lecture Notes in Computer Science 3623, Springer, pp. 19-31, 2005.

  • "Random walks on the vertices of transportation polytopes with a constant number of sources"
    Mary Cryan, Martin Dyer, Haiko Müller and Leen Stougie
    Random Structures and Algorithms 33, 333-355, 2008.
    A preliminary version appeared in
    Proc. 14th Annual Symposium on Discrete Algorithms (SODA 03),
    ACM/SIAM Press, pp. 330-339, 2003.

  • "On counting homomorphisms to directed acyclic graphs"
    Martin Dyer, Leslie Ann Goldberg and Mike Paterson
    Journal of the ACM 54, Article 27, 2007.
    A preliminary version appeared in
    Proc. 33rd International Colloquium on Automata, Languages and Programming (ICALP 06),
    Lecture Notes in Computer Science 4051, Springer, pp. 38-49, 2006.

  • "Sampling regular graphs and a peer-to-peer network"
    Colin Cooper, Martin Dyer and Catherine Greenhill,
    Combinatorics, Probability and Computing 16, 557-593. 2007.
    A preliminary version appeared in
    Proc. 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 05),
    ACM/SIAM Press, pp. 980-988, 2005.

  • "Path coupling without contraction"
    Magnus Bordewich and Martin Dyer
    Journal of Discrete Algorithms 5, 280-292, 2007.

  • "Systematic scan for sampling colourings"
    Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
    Annals of Applied Probability 16, 185-230, 2006.

  • "Markov chain comparison"
    Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and Russell Martin
    Probability Surveys 3, 89-111, 2006.

  • "Randomly coloring sparse random graphs with fewer colors than the maximum degree"
    Martin Dyer, Abie Flaxman, Alan Frieze and Eric Vigoda
    Random Structures and Algorithms 29, 450-465, 2006.

  • "Stopping times, metrics and approximate counting"
    Magnus Bordewich, Martin Dyer and Marek Karpinski
    in Proc. 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006),
    Lecture Notes in Computer Science 4051, Springer, pp. 108-119, 2006.

  • "Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows"
    Mary Cryan, Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and Russell Martin
    SIAM Journal on Computing 36, 247-278, 2006.
    A preliminary version appeared in
    Proc. 43rd Annual Symposium on Foundations of Computer Science (FOCS 02),
    IEEE Computer Society Press, pp. 711-720, 2002.

  • "Computational complexity of stochastic programming problems"
    Martin Dyer and Leen Stougie
    Mathematical Programming 106, 423-432, 2006.

  • "On the sampling problem for H-colorings on the hypercubic lattice"
    Christian Borgs, Jenifer Chayes, Martin Dyer and Prasad Tetali
    in Graphs, Morphisms and Statistical Physics (J Nesetril & P Winkler, eds)
    DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 63,
    American Mathematical Society, 2004, pp. 13-28.

  • "Rapidly mixing Markov chains for dismantleable constraint graphs"
    Martin Dyer, Mark Jerrum and Eric Vigoda
    in Graphs, Morphisms and Statistical Physics (J Nesetril & P Winkler, eds)
    DIMACS Series in Discrete Mathematics and Theoretical Computer Science Vol. 63,
    American Mathematical Society, 2004, pp. 87-96
    A preliminary version appeared in
    Randomization and Approximation Techniques 6th International Workshop (RANDOM 02),
    Lecture Notes in Computer Science 2483, Springer-Verlag, pp. 68-77.

  • "Linear programming"
    Martin Dyer, Nimrod Megiddo and Emo Welzl
    in Handbook of Discrete and Computational Geometry (2nd ed.) (J E Goodman and J O'Rourke, eds)
    CRC Press, 2004, pp. 999-1014.

  • "Counting and sampling H-colourings"
    Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
    Information and Computation 189, 1-16, 2004.
    A preliminary version appeared in
    Randomization and Approximation Techniques 6th International Workshop (RANDOM 02)
    ,
    Lecture Notes in Computer Science 2483, Springer-Verlag, pp. 51-67, 2002.

  • "Mixing in time and space for lattice spin systems: A combinatorial view"
    Martin Dyer, Alistair Sinclair, Eric Vigoda and Dror Weitz
    Random Structures and Algorithms 24, 461-479, 2004.
    A preliminary version appeared in
    Randomization and Approximation Techniques 6th International Workshop (RANDOM 02)
    ,
    Lecture Notes in Computer Science 2483, Springer-Verlag, pp. 149-163, 2002.

  • "On the relative complexity of approximate counting problems"
    Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum
    Algorithmica 38, 471-500, 2003.

  • "Randomly colouring graphs with lower bounds on girth and maximum degree"
    Martin Dyer and Alan Frieze
    Random Structures and Algorithms 23, 167-179, 2003.
    A preliminary version appeared in
    Proc. 42nd IEEE Symposium on Foundations of Computer Science (FOCS 01),
    IEEE Computer Society, pp. 579-587, 2001.

  • "Approximate counting by dynamic programming"
    Martin Dyer
    Proc. 35th Annual ACM Symposium on the Theory of Computing (STOC 03),
    ACM Press, pp. 693-699, 2003.

  • "A probabilistic analysis of randomly generated binary constraint satisfaction problems"
    Martin Dyer, Alan Frieze and Mike Molloy
    Theoretical Computer Science 290, 1815-1828, 2003.

  • "A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant"
    Mary Cryan and Martin Dyer
    Journal of Computer and System Sciences 67, 291-310, 2003. A preliminary version appeared in
    Proc. 34th Annual ACM Symposium on Theory of Computing (STOC 02),
    ACM Press, pp. 240-249, 2002.

  • "Very rapid mixing of the Glauber dynamics for proper colourings on bounded-degree graphs"
    Martin Dyer, Catherine Greenhill and Mike Molloy
    Random Structures and Algorithms 20, 98-114, 2002.

  • "On counting independent sets in sparse graphs"
    Martin Dyer, Alan Frieze and Mark Jerrum
    SIAM Journal on Computing 31, 1527-1541, 2002.

  • "An extension of path coupling and its application to the Glauber dynamics for graph colorings"
    Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Mark Jerrum and Michael Mitzenmacher
    SIAM Journal on Computing 30, 1962-1975, 2001.
    A preliminary version appeared in
    Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 00), pp. 616-624, 2000.

  • "On Markov chains for randomly H-coloring a graph"
    Colin Cooper, Martin Dyer and Alan Frieze
    Journal of Algorithms 39, 117-135, 2001.

  • "Convergence of the iterated prisoner's dilemma game"
    Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill, Gabriel Istrate and Mark Jerrum
    Combinatorics, Probability and Computing 10, 1-13, 2001.

  • "Fast and optimal parallel multidimensional search in PRAMs with applications to linear programming and related problems"
    Martin Dyer and Sandeep Sen
    SIAM Journal on Computing 30, 1443-1461, 2000.

  • "On Markov chains for independent sets"
    Martin Dyer and Catherine Greenhill
    Journal of Algorithms 35, 17-49, 2000.

  • "The complexity of counting graph homomorphisms"
    Martin Dyer and Catherine Greenhill
    Random Structures and Algorithms 17, 260-289, 2000.
    A preliminary version appeared in
    Proc. 11th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 00)
    ,
    ACM/SIAM Press, pp. 246-255, 2000.

  • "On the relative complexity of approximate counting problems"
    Martin Dyer, Leslie Ann Goldberg, Catherine Greenhill and Mark Jerrum
    Approximation Algorithms for Combinatorial Optimization 3rd International Workshop (APPROX 00),
    Lecture Notes in Computer Science 1913, Springer-Verlag, pp. 108-119, 2000.

  • "Polynomial-time counting and sampling of two-rowed contingency tables"
    Martin Dyer and Catherine Greenhill
    Theoretical Computer Science 246, 265-278, 2000.
    A preliminary version appeared as
    "A genuinely polynomial-time algorithms for sampling two-rowed contingency tables",
    Proc. 25th International Colloquium on Automata, Languages and Programming (ICALP 98),
    Lecture Notes in Computer Science 1443, Springer, pp. 339-350, 1998.

  • "Mixing properties of the Swendsen-Wang process on the complete graph and narrow grids"
    Colin Cooper, Martin Dyer, Alan Frieze and Rachel Rue
    Journal of Mathematical Physics 41, 1499-1527, 2000.

  • "On Markov chains for independent sets"
    Martin Dyer and Catherine Greenhill
    Journal of Algorithms 35, pp.17-49, 2000.


  • List of refereed publications before 2000