


default search action
Martin E. Dyer
Person information
- affiliation: University of Leeds, UK
- award (2021): Gödel Prize
- award (1991): Fulkerson Prize
Refine list

refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
showing all ?? records
2020 – today
- 2023
- [j100]Artem Govorov, Jin-Yi Cai, Martin E. Dyer:
A dichotomy for bounded degree graph homomorphisms with nonnegative weights. J. Comput. Syst. Sci. 132: 1-15 (2023) - [i41]Colin Cooper, Martin E. Dyer, Catherine S. Greenhill:
A triangle process on graphs with given degree sequence. CoRR abs/2301.08499 (2023) - [i40]Martin E. Dyer, Haiko Müller:
Thick Forests. CoRR abs/2309.01482 (2023) - 2021
- [j99]Martin E. Dyer
, Marc Heinrich, Mark Jerrum, Haiko Müller
:
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs. Comb. Probab. Comput. 30(6): 905-921 (2021) - [j98]Martin E. Dyer
, Catherine S. Greenhill
, Pieter Kleer
, James Ross, Leen Stougie
:
Sampling hypergraphs with given degrees. Discret. Math. 344(11): 112566 (2021) - [j97]Martin E. Dyer
, Catherine S. Greenhill, Haiko Müller
:
Counting independent sets in graphs with bounded bipartite pathwidth. Random Struct. Algorithms 59(2): 204-237 (2021) - [j96]Martin E. Dyer
, Mark Jerrum
, Haiko Müller
, Kristina Vuskovic:
Counting Weighted Independent Sets beyond the Permanent. SIAM J. Discret. Math. 35(2): 1503-1524 (2021) - [c54]Colin Cooper, Martin E. Dyer
, Catherine S. Greenhill:
A Triangle Process on Regular Graphs. IWOCA 2021: 310-323 - 2020
- [j95]Martin E. Dyer
, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda:
Random Walks on Small World Networks. ACM Trans. Algorithms 16(3): 37:1-37:33 (2020) - [c53]Artem Govorov, Jin-Yi Cai, Martin E. Dyer
:
A Dichotomy for Bounded Degree Graph Homomorphisms with Nonnegative Weights. ICALP 2020: 66:1-66:18 - [i39]Artem Govorov, Jin-Yi Cai, Martin E. Dyer:
A dichotomy for bounded degree graph homomorphisms with nonnegative weights. CoRR abs/2002.02021 (2020) - [i38]Martin E. Dyer, Marc Heinrich, Mark Jerrum, Haiko Müller:
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs. CoRR abs/2005.07944 (2020) - [i37]Martin E. Dyer, Catherine S. Greenhill, Pieter Kleer, James Ross, Leen Stougie:
Sampling hypergraphs with given degrees. CoRR abs/2006.12021 (2020) - [i36]Colin Cooper, Martin E. Dyer, Catherine S. Greenhill:
A triangle process on regular graphs. CoRR abs/2012.12972 (2020)
2010 – 2019
- 2019
- [j94]Colin Cooper, Martin E. Dyer
, Catherine S. Greenhill, Andrew J. Handley:
The flip Markov chain for connected regular graphs. Discret. Appl. Math. 254: 56-79 (2019) - [j93]Martin E. Dyer
, Haiko Müller
:
Quasimonotone graphs. Discret. Appl. Math. 271: 25-48 (2019) - [j92]James Dyer
, Martin E. Dyer
, Jie Xu:
Practical homomorphic encryption over the integers for secure computation in the cloud. Int. J. Inf. Sec. 18(5): 549-579 (2019) - [j91]Martin E. Dyer
, Haiko Müller
:
Counting independent sets in cocomparability graphs. Inf. Process. Lett. 144: 31-36 (2019) - [j90]James Dyer
, Martin E. Dyer
, Karim Djemame
:
Order-preserving encryption using approximate common divisors. J. Inf. Secur. Appl. 49 (2019) - [j89]Martin E. Dyer
, Haiko Müller
:
Counting Perfect Matchings and the Switch Chain. SIAM J. Discret. Math. 33(3): 1146-1174 (2019) - [c52]Martin E. Dyer
, Catherine S. Greenhill, Haiko Müller
:
Counting Independent Sets in Graphs with Bounded Bipartite Pathwidth. WG 2019: 298-310 - [i35]Colin Cooper, Martin E. Dyer, Catherine S. Greenhill:
Triangle-creation processes on cubic graphs. CoRR abs/1905.04490 (2019) - [i34]Martin E. Dyer, Mark Jerrum, Haiko Müller
, Kristina Vuskovic:
Counting weighted independent sets beyond the permanent. CoRR abs/1909.03414 (2019) - 2018
- [j88]Colin Cooper
, Martin E. Dyer
, Alan M. Frieze, Nicolás Rivera:
Discordant Voting Processes on Finite Graphs. SIAM J. Discret. Math. 32(4): 2398-2420 (2018) - [c51]Martin E. Dyer
, Haiko Müller
:
Quasimonotone Graphs. WG 2018: 190-202 - [i33]Martin E. Dyer, Haiko Müller:
Quasimonotone graphs. CoRR abs/1801.06494 (2018) - [i32]Martin E. Dyer, Haiko Müller:
Counting Independent Sets in Cocomparability Graphs. CoRR abs/1808.09853 (2018) - [i31]Martin E. Dyer, Catherine S. Greenhill, Haiko Müller:
Counting independent sets in graphs with bounded bipartite pathwidth. CoRR abs/1812.03195 (2018) - 2017
- [j87]Martin E. Dyer
, Mark Jerrum, Haiko Müller
:
On the Switch Markov Chain for Perfect Matchings. J. ACM 64(2): 12:1-12:33 (2017) - [c50]James Dyer
, Martin E. Dyer
, Jie Xu:
Order-Preserving Encryption Using Approximate Integer Common Divisors. DPM/CBT@ESORICS 2017: 257-274 - [c49]James Dyer
, Martin E. Dyer
, Jie Xu:
Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud. IMACC 2017: 44-76 - [i30]Colin Cooper, Martin E. Dyer, Catherine S. Greenhill, Andrew J. Handley:
The flip Markov chain for connected regular graphs. CoRR abs/1701.03856 (2017) - [i29]James Dyer
, Martin E. Dyer, Jie Xu:
Practical Homomorphic Encryption Over the Integers. CoRR abs/1702.07588 (2017) - [i28]Martin E. Dyer, Haiko Müller:
Counting perfect matchings and the switch chain. CoRR abs/1705.05790 (2017) - [i27]James Dyer, Martin E. Dyer, Jie Xu:
Order-Preserving Encryption Using Approximate Integer Common Divisors. CoRR abs/1706.00324 (2017) - [i26]Martin E. Dyer, Andreas Galanis, Leslie Ann Goldberg, Mark Jerrum, Eric Vigoda:
Random Walks on Small World Networks. CoRR abs/1707.02467 (2017) - 2016
- [j86]Martin E. Dyer
, Leslie Ann Goldberg, David Richerby
:
Counting 4×4 matrix partitions of graphs. Discret. Appl. Math. 213: 76-92 (2016) - [c48]Colin Cooper, Martin E. Dyer
, Alan M. Frieze, Nicolas Rivera:
Discordant Voting Processes on Finite Graphs. ICALP 2016: 145:1-145:13 - [c47]Martin E. Dyer
, Mark Jerrum, Haiko Müller
:
On the switch Markov chain for perfect matchings. SODA 2016: 1972-1983 - [i25]Colin Cooper, Martin E. Dyer, Alan M. Frieze, Nicolas Rivera:
Discordant voting processes on finite graphs. CoRR abs/1604.06884 (2016) - 2015
- [j85]Xi Chen, Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu
, Colin McQuillan, David Richerby
:
The complexity of approximating conservative counting CSPs. J. Comput. Syst. Sci. 81(1): 311-329 (2015) - [j84]Martin E. Dyer
, Alan M. Frieze
, Catherine S. Greenhill:
On the chromatic number of a random hypergraph. J. Comb. Theory B 113: 68-122 (2015) - [j83]Martin E. Dyer
, Leen Stougie:
Erratum to: Computational complexity of stochastic programming problems. Math. Program. 153(2): 723-725 (2015) - [i24]Martin E. Dyer, Mark Jerrum, Haiko Müller:
On the switch Markov chain for perfect matchings. CoRR abs/1501.07725 (2015) - 2014
- [j82]Martin E. Dyer
, Ravi Kannan, Leen Stougie:
A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming. Math. Program. 147(1-2): 207-229 (2014) - [i23]Martin E. Dyer, Leslie Ann Goldberg, David Richerby:
Counting 4×4 Matrix Partitions of Graphs. CoRR abs/1407.7799 (2014) - 2013
- [j81]Andrei A. Bulatov, Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum, Colin McQuillan:
The expressibility of functions on the boolean domain, with applications to counting CSPs. J. ACM 60(5): 32:1-32:36 (2013) - [j80]Martin E. Dyer
, Alan M. Frieze
, Thomas P. Hayes, Eric Vigoda:
Randomly coloring constant degree graphs. Random Struct. Algorithms 43(2): 181-200 (2013) - [j79]Martin E. Dyer
, David Richerby
:
An Effective Dichotomy for the Counting Constraint Satisfaction Problem. SIAM J. Comput. 42(3): 1245-1274 (2013) - [c46]Xi Chen, Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu
, Colin McQuillan, David Richerby
:
The complexity of approximating conservative counting CSPs. STACS 2013: 148-159 - 2012
- [j78]Martin E. Dyer
, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
:
The complexity of approximating bounded-degree Boolean #CSP. Inf. Comput. 220: 1-14 (2012) - [j77]Andrei A. Bulatov, Martin E. Dyer
, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby
:
The complexity of weighted and unweighted #CSP. J. Comput. Syst. Sci. 78(2): 681-688 (2012) - [c45]Andrei A. Bulatov, Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum:
Log-supermodular functions, functional clones and counting CSPs. STACS 2012: 302-313 - [i22]Martin E. Dyer, Alan M. Frieze, Catherine S. Greenhill:
On the chromatic number of a random hypergraph. CoRR abs/1208.0812 (2012) - [i21]Xi Chen, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum, Pinyan Lu, Colin McQuillan, David Richerby:
The complexity of approximating conservative counting CSPs. CoRR abs/1208.1783 (2012) - 2011
- [c44]Martin E. Dyer
, Velumailum Mohanaraj:
Pairwise-Interaction Games. ICALP (1) 2011: 159-170 - [c43]Colin Cooper, Martin E. Dyer
, Andrew J. Handley:
Networks of random cycles. SODA 2011: 933-944 - [c42]Martin E. Dyer
, David Richerby
:
The #CSP Dichotomy is Decidable. STACS 2011: 261-272 - [i20]Martin E. Dyer, Velumailum Mohanaraj:
The Iterated Prisoner's Dilemma on a Cycle. CoRR abs/1102.3822 (2011) - [i19]Colin Cooper, Martin E. Dyer, Velumailum Mohanaraj:
On the Imitation Strategy for Games on Graphs. CoRR abs/1102.3879 (2011) - [i18]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
Log-supermodular functions, functional clones and counting CSPs. CoRR abs/1108.5288 (2011) - [i17]Martin E. Dyer, Uriel Feige, Alan M. Frieze, Marek Karpinski:
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241). Dagstuhl Reports 1(6): 24-53 (2011) - 2010
- [j76]Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum:
A Complexity Dichotomy For Hypergraph Partition Functions. Comput. Complex. 19(4): 605-633 (2010) - [j75]Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum:
An approximation trichotomy for Boolean #CSP. J. Comput. Syst. Sci. 76(3-4): 267-277 (2010) - [j74]Martin E. Dyer
, Alan M. Frieze
:
Randomly coloring random graphs. Random Struct. Algorithms 36(3): 251-272 (2010) - [j73]Mary Cryan, Martin E. Dyer
, Dana Randall:
Approximately Counting Integral Flows and Cell-Bounded Contingency Tables. SIAM J. Comput. 39(7): 2683-2703 (2010) - [c41]Martin E. Dyer
, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
:
The Complexity of Approximating Bounded-Degree Boolean #CSP. STACS 2010: 323-334 - [c40]Martin E. Dyer
, David Richerby
:
On the complexity of #CSP. STOC 2010: 725-734 - [i16]Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby:
The Complexity of Approximating Bounded-Degree Boolean #CSP (Extended Abstract). CoRR abs/1001.4987 (2010) - [i15]Martin E. Dyer, David Richerby:
The Complexity of #CSP. CoRR abs/1003.3879 (2010) - [i14]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, Mark Jerrum, David Richerby:
The complexity of weighted and unweighted #CSP. CoRR abs/1005.2678 (2010)
2000 – 2009
- 2009
- [j72]Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum:
The Complexity of Weighted Boolean #CSP. SIAM J. Comput. 38(5): 1970-1986 (2009) - [j71]Andrei A. Bulatov, Martin E. Dyer
, Leslie Ann Goldberg, Markus Jalsenius, David Richerby
:
The complexity of weighted Boolean #CSP with mixed signs. Theor. Comput. Sci. 410(38-40): 3949-3961 (2009) - [c39]Colin Cooper, Martin E. Dyer
, Andrew J. Handley:
The flip markov chain and a randomising P2P protocol. PODC 2009: 141-150 - [i13]Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby:
The Complexity of Approximating Bounded-Degree Boolean #CSP. CoRR abs/0907.2663 (2009) - 2008
- [j70]Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum:
Dobrushin Conditions and Systematic Scan. Comb. Probab. Comput. 17(6): 761-779 (2008) - [j69]Magnus Bordewich
, Martin E. Dyer
, Marek Karpinski:
Path coupling using stopping times and counting independent sets and colorings in hypergraphs. Random Struct. Algorithms 32(3): 375-399 (2008) - [j68]Mary Cryan, Martin E. Dyer
, Haiko Müller
, Leen Stougie:
Random walks on the vertices of transportation polytopes with constant number of sources. Random Struct. Algorithms 33(3): 333-355 (2008) - [e2]Martin E. Dyer, Mark Jerrum, Marek Karpinski:
Design and Analysis of Randomized and Approximation Algorithms, 11.05. - 16.05.2008. Dagstuhl Seminar Proceedings 08201, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2008 [contents] - [i12]Martin E. Dyer, Mark Jerrum, Marek Karpinski:
08201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. Design and Analysis of Randomized and Approximation Algorithms 2008 - [i11]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
A complexity dichotomy for hypergraph partition functions. CoRR abs/0811.0037 (2008) - [i10]Andrei A. Bulatov, Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby:
The Complexity of Weighted Boolean #CSP with Mixed Signs. CoRR abs/0812.4171 (2008) - 2007
- [j67]Colin Cooper, Martin E. Dyer
, Catherine S. Greenhill:
Sampling Regular Graphs and a Peer-to-Peer Network. Comb. Probab. Comput. 16(4): 557-593 (2007) - [j66]Martin E. Dyer
, Leslie Ann Goldberg, Mike Paterson:
On counting homomorphisms to directed acyclic graphs. J. ACM 54(6): 27 (2007) - [j65]Magnus Bordewich
, Martin E. Dyer
:
Path coupling without contraction. J. Discrete Algorithms 5(2): 280-292 (2007) - [i9]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
The Complexity of Weighted Boolean #CSP. CoRR abs/0704.3683 (2007) - [i8]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
An approximation trichotomy for Boolean #CSP. CoRR abs/0710.4272 (2007) - [i7]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
Matrix norms and rapid mixing for spin systems. CoRR abs/math/0702744 (2007) - 2006
- [j64]Martin E. Dyer
, Leen Stougie:
Computational complexity of stochastic programming problems. Math. Program. 106(3): 423-432 (2006) - [j63]Martin E. Dyer
, Abraham D. Flaxman, Alan M. Frieze
, Eric Vigoda:
Randomly coloring sparse random graphs with fewer colors than the maximum degree. Random Struct. Algorithms 29(4): 450-465 (2006) - [j62]Mary Cryan, Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum, Russell A. Martin:
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows. SIAM J. Comput. 36(1): 247-278 (2006) - [c38]Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum:
Dobrushin Conditions and Systematic Scan. APPROX-RANDOM 2006: 327-338 - [c37]Martin E. Dyer
, Leslie Ann Goldberg, Mike Paterson:
On Counting Homomorphisms to Directed Acyclic Graphs. ICALP (1) 2006: 38-49 - [c36]Magnus Bordewich
, Martin E. Dyer
, Marek Karpinski:
Stopping Times, Metrics and Approximate Counting. ICALP (1) 2006: 108-119 - 2005
- [c35]Magnus Bordewich
, Martin E. Dyer
, Marek Karpinski:
Path Coupling Using Stopping Times. FCT 2005: 19-31 - [c34]Colin Cooper, Martin E. Dyer, Catherine S. Greenhill:
Sampling regular graphs and a peer-to-peer network. SODA 2005: 980-988 - [c33]Mary Cryan, Martin E. Dyer
, Dana Randall:
Approximately counting integral flows and cell-bounded contingency tables. STOC 2005: 413-422 - [e1]Martin E. Dyer, Mark Jerrum, Marek Karpinski:
Design and Analysis of Randomized and Approximation Algorithms, 15.05. - 20.05.2005. Dagstuhl Seminar Proceedings 05201, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany 2005 [contents] - [i6]Martin E. Dyer, Mark Jerrum, Marek Karpinski:
05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms. Design and Analysis of Randomized and Approximation Algorithms 2005 - [i5]Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs. Electron. Colloquium Comput. Complex. TR05 (2005) - [i4]Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum:
Dobrushin conditions and Systematic Scan. Electron. Colloquium Comput. Complex. TR05 (2005) - [i3]Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson:
On counting homomorphisms to directed acyclic graphs. Electron. Colloquium Comput. Complex. TR05 (2005) - [i2]Magnus Bordewich, Martin E. Dyer, Marek Karpinski:
Metric Construction, Stopping Times and Path Coupling. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j61]Martin E. Dyer
, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum:
The Relative Complexity of Approximate Counting Problems. Algorithmica 38(3): 471-500 (2004) - [j60]Martin E. Dyer
, Leslie Ann Goldberg, Mark Jerrum:
Counting and sampling H-colourings? Inf. Comput. 189(1): 1-16 (2004) - [j59]Martin E. Dyer
, Alistair Sinclair, Eric Vigoda, Dror Weitz:
Mixing in time and space for lattice spin systems: A combinatorial view. Random Struct. Algorithms 24(4): 461-479 (2004) - [j58]Martin E. Dyer
, Catherine S. Greenhill:
Corrigendum: The complexity of counting graph homomorphisms. Random Struct. Algorithms 25(3): 346-352 (2004) - [c32]Martin E. Dyer
, Alan M. Frieze
, Thomas P. Hayes, Eric Vigoda:
Randomly Coloring Constant Degree Graphs. FOCS 2004: 582-589 - [r1]Martin E. Dyer, Nimrod Megiddo, Emo Welzl:
Linear programming. Handbook of Discrete and Computational Geometry, 2nd Ed. 2004: 999-1014 - [i1]Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda:
Randomly coloring constant degree graphs. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j57]Mary Cryan, Martin E. Dyer
:
A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. J. Comput. Syst. Sci. 67(2): 291-310 (2003) - [j56]Martin E. Dyer
, Alan M. Frieze
:
Randomly coloring graphs with lower bounds on girth and maximum degree. Random Struct. Algorithms 23(2): 167-179 (2003) - [j55]Martin E. Dyer
, Alan M. Frieze
, Michael Molloy:
A probabilistic analysis of randomly generated binary constraint satisfaction problems. Theor. Comput. Sci. 290(3): 1815-1828 (2003) - [c31]Sammani D. Abdullahi, Martin E. Dyer
, Les G. Proll:
Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems. DMTCS 2003: 89-96 - [c30]Mary Cryan, Martin E. Dyer, Haiko Müller, Leen Stougie:
Random walks on the vertices of transportation polytopes with constant number of sources. SODA 2003: 330-339 - [c29]Martin E. Dyer
:
Approximate counting by dynamic programming. STOC 2003: 693-699 - 2002
- [j54]Martin E. Dyer
, Leslie Ann Goldberg, Catherine S. Greenhill, Gabriel Istrate, Mark Jerrum:
Convergence Of The Iterated Prisoner's Dilemma Game. Comb. Probab. Comput. 11(2): 135-147 (2002) - [j53]Martin E. Dyer
, Catherine S. Greenhill, Michael Molloy:
Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs. Random Struct. Algorithms 20(1): 98-114 (2002) - [j52]Martin E. Dyer
, Alan M. Frieze
, Mark Jerrum:
On Counting Independent Sets in Sparse Graphs. SIAM J. Comput. 31(5): 1527-1541 (2002) - [c28]