Random Walks on Small World Networks
Martin Dyer, Andreas Galanis, Leslie Anne Goldberg, Mark Jerrum and Eric Vigoda ACM Transactions on Algorithms, 16.3, 2020.
Quasimonotone graphs
Martin Dyer and Haiko Müller Discrete Applied Mathematics271, 25-48, 2019.
“On the switch Markov chain for perfect matchings”
Martin Dyer, Mark Jerrum and Haiko Müller Journal of the ACM 64, Article 12, 2017.
A preliminary version appeared in Proc. 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016)
ACM/SIAM Press, pp. 1972-1983, 2016.
“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 Sciences81, 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.
“An effective dichotomy for the counting constraint satisfaction problem”
Martin Dyer and David Richerby SIAM Journal on Computing42, 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 Algorithms43, 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 Computation220-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 Sciences78, 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.
“Approximately counting integral flows and cell-bounded contingency tables”
Mary Cryan, Martin Dyer and Dana Randall SIAM Journal on Computing30, 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.
“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.
“Dobrushin conditions and systematic scan”
Martin Dyer, Leslie Ann Goldberg and Mark Jerrum Combinatorics, Probability and Computing17, 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.
“On counting homomorphisms to directed acyclic graphs”
Martin Dyer, Leslie Ann Goldberg and Mike Paterson Journal of the ACM54, 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 Computing16, 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.
“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.
“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 Computation189, 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 Algorithms24, 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.
“Randomly colouring graphs with lower bounds on girth and maximum degree”
Martin Dyer and Alan Frieze Random Structures and Algorithms23, 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.
“On Markov chains for randomly H-coloring a graph”
Colin Cooper, Martin Dyer and Alan Frieze Journal of Algorithms39, 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 Computing10, 1-13, 2001.
“On Markov chains for independent sets”
Martin Dyer and Catherine Greenhill Journal of Algorithms35, 17-49, 2000.
“The complexity of counting graph homomorphisms”
Martin Dyer and Catherine Greenhill Random Structures and Algorithms17, 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 Science246, 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.