Martin Dyer

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.

Older publications (Pre-2000, not linked)