Research Activity -
Algorithms and Complexity

Martin Dyer

Martin Dyer's Papers

Preprints

• "A complexity dichotomy for hypergraph partition functions "
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
  
  
• "On the complexity of #CSP"
  Martin Dyer and David Richerby
  
  
• "The complexity of weighted and unweighted #CSP"
  Andrei Bulatov, Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum and David Richerby
  

Publications (2000-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 05),
  ACM Press, pp. 413-422, 2005.
  
  
• "The complexity of approximating bounded-degree Boolean #CSP"
  Martin Dyer, Leslie Ann Goldberg, Markus Jalsenius and David Richerby
  in Proc. 27th International Symposium on Theoretical Aspects of Computer Science (STACS 2010),
  Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 323-334, 2010.
  
  
• "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, 36, 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.
  
  
• "Randomly coloring constant degree graphs"
  Martin Dyer, Alan Frieze, Thomas P. Hayes and Eric Vigoda
  in Proc. 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 04),
  IEEE Computer Society Press, pp. 582-589, 2004.
  
  
• "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 Welz
  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.