Research Activity -
Algorithms and Complexity

Martin Dyer

Martin Dyer's Papers

Preprints

• "An approximation trichotomy for Boolean #CSP"
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
  arXiv:0710.4272v1 [cs.CC], October 2007.
• "The complexity of weighted Boolean #CSP"
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
  arXiv:0704.3683v1 [cs.CC], April 2007. (Submitted for publication.)
• "Matrix norms and rapid mixing for spin systems"
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
  arXiv:math/0702744v1 [math.PR], February 2007. (Submitted for publication).

Recent Publications (2000-2007)

• "On counting homomorphisms to directed acyclic graphs"
  Martin Dyer, Leslie Ann Goldberg and Mike Paterson
  Journal of the ACM 54, Article 27, 2007. PDF
  A preliminary version appeared in
  Proceedings of the 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. PDF

A preliminary version appeared in
Proceedings of the 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. PDF
• "Systematic scan for sampling colourings"
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
  Annals of Applied Probability 16, 185-230. 2006. PDF
• "Markov chain comparison"
  Martin Dyer, Leslie Ann Goldberg, Mark Jerrum and  Russell Martin
  Probability Surveys 3, 89-111. 2006. PDF
• "Dobrushin conditions and systematic scan"
  Martin Dyer, Leslie Ann Goldberg and Mark Jerrum
  in Proceedings of the 10th International Workshop on Randomization and Computation (RANDOM 06),
  Lecture Notes in Computer Science 4110, Springer, pp. 327-338. PDF
• "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.  PDF
• "Stopping times, metrics and approximate counting"
  Magnus Bordewich, Martin Dyer and Marek Karpinski
  in Proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006),
  Lecture Notes in Computer Science 4051, Springer, pp. 108-119, 2006.  PDF
• "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. PS
  A preliminary version appeared in
  Proceedings of the 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. PDF
• "Path coupling using stopping times"
  Magnus Bordewich, Martin Dyer and Marek Karpinski
  in Proceedings of the 15th Annual Symposium on Fundamentals of Computation Theory (FCT 05),
  Lecture Notes in Computer Science 3623, Springer, pp. 19-31, 2005. PDF
• "Randomly coloring constant degree graphs"
  Martin Dyer, Alan Frieze, Thomas P. Hayes and Eric Vigoda
  in Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS 04),
  EEE Computer Society Press, pp. 582-589, 2004. PDF
• "Approximately counting integral flows and cell-bounded contingency tables"
  Mary Cryan, Martin Dyer and Dana Randall
  in Proceedings of the 37th Annual ACM Symposium on the Theory of Computing (STOC 05),
  ACM Press, pp. 413-422, 2005.
  Full paper submitted to SIAM Journal on Computing. PDF
• "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. PDF
• "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 PS
  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, pp. 1-16, 2004. PS
  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, pp. 461-479, 2004. PDF
  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, pp. 471-500, 2003. PS


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


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


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


• "Random walks on the vertices of transportation polytopes with a constant number of sources"
  Mary Cryan, Martin Dyer, Haiko Müller and Leen Stougie
  Proceedings of the 14th Annual Symposium on Discrete Algorithms (SODA 03),
  ACM/SIAM Press. pp. 330-339, 2003. PS


• "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, pp. 98-114, 2002. PS


• "A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant"
  Mary Cryan and Martin Dyer
  Proceedings of the 34th Annual ACM Symposium on Theory of Computing (STOC 02),
  ACM Press, pp. 240-249, 2002. PS
  Full paper to appear in the STOC 02 issue of Journal of Computer and System Sciences. PS


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


• "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, pp. 1962-1975, 2001. PDF
  A preliminary version appeared in
  Proceedings of the 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, pp. 117-135, 2001. PDF


• "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, pp. 1-13, 2001. PDF


• "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, pp. 1443-1461, 2000. PDF


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


• "The complexity of counting graph homomorphisms"
  Martin Dyer and Catherine Greenhill
  Random Structures and Algorithms 17, pp. 260-289, 2000. PDF
  A preliminary version appeared in
  Proceedings of the 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. PDF


• "Polynomial-time counting and sampling of two-rowed contingency tables"
  Martin Dyer and Catherine Greenhill
  Theoretical Computer Science 246, pp. 265-278, 2000. PDF
  A preliminary version appeared as
  "A genuinely polynomial-time algorithms for sampling two-rowed contingency tables",
  Proceedings of the 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, pp. 1499-1527, 2000. PS
• "On Markov chains for independent sets"
  Martin Dyer and Catherine Greenhill
  Journal of Algorithms 35, pp.17-49, 2000.  PS

Some older publications are listed here.