# Martin Dyer

- Position
- Emeritus Professor
- M.E.Dyer@leeds.ac.uk

**Publications**

**Preprints**

- A triangle process on regular graphs

Colin Cooper. Martin Dyer and Catherine Greenhill

Extended abstract to appear in*Proceedings of IWOCA 21*. - Sampling hypergraphs with given degrees

Martin Dyer, Catherine Greenhill, Pieter Kleer, James Ross and Leen Stougie

To appear in*Discrete Mathematics*.

**Refereed Publications (from 2000)**

- Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs

Martin Dyer, Marc Heinrich, Mark Jerrum and Haiko Müller

*Combinatorics, Probability and Computing*, 1-17, 2021. - Counting weighted independent sets beyond the permanent

Martin Dyer, Mark Jerrum, Haiko Müller and Kristina Vuskovic

*SIAM Journal on Discrete Mathematics*, 2021. - Counting independent sets in graphs with bounded bipartite pathwidth

Martin Dyer, Catherine Greenhill and Haiko Müller

*Random Structures & Algorithms*, 2021. - 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 Mathematics***271,**25-48, 2019. - Order-Preserving Encryption Using Approximate Common Divisors

James Dyer, Martin Dyer and Karim Djemame

*Journal of Information Security and Applications***49**, Article 102391**,**2019. - Practical homomorphic encryption over the integers for secure computation in the cloud

James Dyer, Martin Dyer and Jie Xu

*International Journal of Information Security***18.**5, 549-579, 2019. - Counting Perfect Matchings and the Switch Chain

Martin Dyer and Haiko Müller

*SIAM Journal on Discrete Mathematics***33**.3, 1146-1174, 2019. - Counting Independent Sets in Cocomparability Graphs

Martin Dyer and Haiko Müller

*Information Processing Letters***144**, 31-36, 2019. - The flip Markov chain for connected regular graphs

Colin Cooper, Martin Dyer, Catherine Greenhill and Andrew Handley

*Discrete Applied Mathematics***254**, 56-79, 2019. - Discordant Voting Processes on Finite Graphs

Colin Cooper, Martin Dyer, Alan Frieze and Nicolas Rivera

*SIAM Journal on Discrete Mathematics***32**.4, 2398-2420, 2018.

- Order-Preserving Encryption Using Approximate Common Divisors

James Dyer, Martin Dyer and Karim Djemame

*Journal of Information Security and Applications***49**, Article 102391**,**2019. - Practical homomorphic encryption over the integers for secure computation in the cloud

James Dyer, Martin Dyer and Jie Xu

*International Journal of Information Security***18.**5, 549-579, 2019. - Counting Independent Sets in Cocomparability Graphs

Martin Dyer and Haiko Müller

*Information Processing Letters***144**, 31-36, 2019. - The flip Markov chain for connected regular graphs

Colin Cooper, Martin Dyer, Catherine Greenhill and Andrew Handley

*Discrete Applied Mathematics***254**, 56-79, 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. - "Counting 4 x 4 matrix partitions of graphs"

Martin Dyer, Leslie Ann Goldberg and David Richerby

*Discrete Applied Mathematics***213**, 76-92, 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"

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.