Coauthor Index - Ask others: ACM DL/Guide - CiteSeerX - CSB - MetaPress - Google - Bing - Yahoo

* | 2009 | |
---|---|---|

105 | EE | Colin Cooper, Martin E. Dyer, Andrew J. Handley: The flip markov chain and a randomising P2P protocol. PODC 2009: 141-150 |

104 | EE | Martin E. Dyer, Leslie Ann Goldberg, Markus Jalsenius, David Richerby: The Complexity of Approximating Bounded-Degree Boolean #CSP CoRR abs/0907.2663: (2009) |

103 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: The Complexity of Weighted Boolean CSP. SIAM J. Comput. 38(5): 1970-1986 (2009) |

102 | EE | Andrei 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) |

2008 | ||

101 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: A complexity dichotomy for hypergraph partition functions CoRR abs/0811.0037: (2008) |

100 | EE | Andrei 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) |

99 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin Conditions and Systematic Scan. Combinatorics, Probability & Computing 17(6): 761-779 (2008) |

98 | EE | 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) |

97 | EE | 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) |

2007 | ||

96 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: The Complexity of Weighted Boolean #CSP CoRR abs/0704.3683: (2007) |

95 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: An approximation trichotomy for Boolean #CSP CoRR abs/0710.4272: (2007) |

94 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Matrix norms and rapid mixing for spin systems CoRR abs/math/0702744: (2007) |

93 | EE | Colin Cooper, Martin E. Dyer, Catherine S. Greenhill: Sampling Regular Graphs and a Peer-to-Peer Network. Combinatorics, Probability & Computing 16(4): 557-593 (2007) |

92 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On counting homomorphisms to directed acyclic graphs. J. ACM 54(6): (2007) |

91 | EE | Magnus Bordewich, Martin E. Dyer: Path coupling without contraction. J. Discrete Algorithms 5(2): 280-292 (2007) |

2006 | ||

90 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin Conditions and Systematic Scan. APPROX-RANDOM 2006: 327-338 |

89 | EE | Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Stopping Times, Metrics and Approximate Counting. ICALP (1) 2006: 108-119 |

88 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On Counting Homomorphisms to Directed Acyclic Graphs. ICALP (1) 2006: 38-49 |

87 | EE | Martin E. Dyer, Leen Stougie: Computational complexity of stochastic programming problems. Math. Program. 106(3): 423-432 (2006) |

86 | EE | 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) |

85 | EE | 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) |

2005 | ||

84 | EE | Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Path Coupling Using Stopping Times. FCT 2005: 19-31 |

83 | EE | Colin Cooper, Martin E. Dyer, Catherine S. Greenhill: Sampling regular graphs and a peer-to-peer network. SODA 2005: 980-988 |

82 | EE | Mary Cryan, Martin E. Dyer, Dana Randall: Approximately counting integral flows and cell-bounded contingency tables. STOC 2005: 413-422 |

81 | EE | Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs Electronic Colloquium on Computational Complexity (ECCC)(002): (2005) |

80 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Dobrushin conditions and Systematic Scan Electronic Colloquium on Computational Complexity (ECCC)(075): (2005) |

79 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mike Paterson: On counting homomorphisms to directed acyclic graphs Electronic Colloquium on Computational Complexity (ECCC)(121): (2005) |

78 | EE | Magnus Bordewich, Martin E. Dyer, Marek Karpinski: Metric Construction, Stopping Times and Path Coupling. Electronic Colloquium on Computational Complexity (ECCC)(151): (2005) |

2004 | ||

77 | EE | Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda: Randomly Coloring Constant Degree Graphs. FOCS 2004: 582-589 |

76 | EE | Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda: Randomly coloring constant degree graphs Electronic Colloquium on Computational Complexity (ECCC)(009): (2004) |

75 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Counting and sampling H-colourings? Inf. Comput. 189(1): 1-16 (2004) |

74 | EE | 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) |

73 | EE | Martin E. Dyer, Catherine S. Greenhill: Corrigendum: The complexity of counting graph homomorphisms. Random Struct. Algorithms 25(3): 346-352 (2004) |

2003 | ||

72 | EE | Sammani D. Abdullahi, Martin E. Dyer, Les G. Proll: Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems. DMTCS 2003: 89-96 |

71 | EE | 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 |

70 | EE | Martin E. Dyer: Approximate counting by dynamic programming. STOC 2003: 693-699 |

69 | EE | Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum: The Relative Complexity of Approximate Counting Problems. Algorithmica 38(3): 471-500 (2003) |

68 | EE | 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) |

67 | EE | 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) |

66 | 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) | |

2002 | ||

65 | EE | 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. FOCS 2002: 711-720 |

64 | EE | Martin E. Dyer, Alistair Sinclair, Eric Vigoda, Dror Weitz: Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View. RANDOM 2002: 149-163 |

63 | EE | Martin E. Dyer, Leslie Ann Goldberg, Mark Jerrum: Counting and Sampling H-Colourings. RANDOM 2002: 51-67 |

62 | EE | Martin E. Dyer, Mark Jerrum, Eric Vigoda: Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs. RANDOM 2002: 68-77 |

61 | EE | Mary Cryan, Martin E. Dyer: A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant. STOC 2002: 240-249 |

60 | Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Gabriel Istrate, Mark Jerrum: Convergence Of The Iterated Prisoner's Dilemma Game Combinatorics, Probability & Computing 11(2): (2002) | |

59 | 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) | |

58 | EE | Martin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. SIAM J. Comput. 31(5): 1527-1541 (2002) |

2001 | ||

57 | Martin E. Dyer, Alan M. Frieze: Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree. FOCS 2001: 579-587 | |

56 | Colin Cooper, Martin E. Dyer, Alan M. Frieze: On Markov Chains for Randomly H-Coloring a Graph. J. Algorithms 39(1): 117-134 (2001) | |

2000 | ||

55 | EE | Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum: On the relative complexity of approximate counting problems. APPROX 2000: 108-119 |

54 | EE | Martin E. Dyer, Catherine S. Greenhill: The complexity of counting graph homomorphisms (extended abstract). SODA 2000: 246-255 |

53 | EE | Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher: An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). SODA 2000: 616-624 |

52 | Martin E. Dyer, Catherine S. Greenhill: On Markov Chains for Independent Sets. J. Algorithms 35(1): 17-49 (2000) | |

51 | Martin E. Dyer, Catherine S. Greenhill: The complexity of counting graph homomorphisms. Random Struct. Algorithms 17(3-4): 260-289 (2000) | |

50 | EE | Martin E. Dyer, Sandeep Sen: Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems. SIAM J. Comput. 30(5): 1443-1461 (2000) |

49 | EE | Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher: An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings. SIAM J. Comput. 30(6): 1962-1975 (2000) |

48 | EE | Martin E. Dyer, Catherine S. Greenhill: Polynomial-time counting and sampling of two-rowed contingency tables. Theor. Comput. Sci. 246(1-2): 265-278 (2000) |

1999 | ||

47 | EE | Martin E. Dyer, Alan M. Frieze, Mark Jerrum: On Counting Independent Sets in Sparse Graphs. FOCS 1999: 210-217 |

46 | EE | Russ Bubley, Martin E. Dyer: Faster random generation of linear extensions. Discrete Mathematics 201(1-3): 81-88 (1999) |

45 | Russ Bubley, Martin E. Dyer, Catherine S. Greenhill, Mark Jerrum: On Approximately Counting Colorings of Small Degree Graphs. SIAM J. Comput. 29(2): 387-400 (1999) | |

1998 | ||

44 | EE | Martin E. Dyer, Catherine S. Greenhill: A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables. ICALP 1998: 339-350 |

43 | Russ Bubley, Martin E. Dyer: Faster Random Generation of Linear Extensions. SODA 1998: 350-354 | |

42 | Russ Bubley, Martin E. Dyer, Catherine S. Greenhill: Beating the 2 Delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing. SODA 1998: 355-363 | |

41 | Russ Bubley, Martin E. Dyer, Mark Jerrum: An elementary analysis of a procedure for sampling points in a convex body. Random Struct. Algorithms 12(3): 213-235 (1998) | |

40 | Martin E. Dyer, Catherine S. Greenhill: A more rapidly mixing Markov chain for graph colorings. Random Struct. Algorithms 13(3-4): 285-317 (1998) | |

39 | Martin E. Dyer, Peter Gritzmann, Alexander Hufnagel: On the Complexity of Computing Mixed Volumes. SIAM J. Comput. 27(2): 356-400 (1998) | |

38 | EE | Martin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Paths and Cycles in Dense Graphs. SIAM J. Comput. 27(5): 1262-1272 (1998) |

1997 | ||

37 | EE | Russ Bubley, Martin E. Dyer: Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains. FOCS 1997: 223-231 |

36 | Russ Bubley, Martin E. Dyer: Graph Orientations with No Sink and an Approximation for a Hard Case of #SAT. SODA 1997: 248-257 | |

35 | Martin E. Dyer, Ravi Kannan, John Mount: Sampling contingency tables. Random Struct. Algorithms 10(4): 487-506 (1997) | |

1996 | ||

34 | EE | Jonathan M. Nash, Peter M. Dew, John R. Davy, Martin E. Dyer: Implementation Issues Relating to the WPRAM Model for Scalable Computing. Euro-Par, Vol. II 1996: 319-326 |

33 | EE | Barbara M. Smith, Martin E. Dyer: Locating the Phase Transition in Binary Constraint Satisfaction Problems. Artif. Intell. 81(1-2): 155-181 (1996) |

32 | Jonathan M. Nash, Peter M. Dew, Martin E. Dyer: A Scalable Shared Queue on a Distributed Memory Machine. Comput. J. 39(6): 483-495 (1996) | |

1995 | ||

31 | EE | Martin E. Dyer, Jonathan M. Nash, Peter M. Dew: An Optimal Randomized Planar Convex Hull Algorithm With Good Empirical Performance. SPAA 1995: 21-26 |

30 | EE | Martin E. Dyer: A Parallel Algorithm for Linear Programming in Fixed Dimension. Symposium on Computational Geometry 1995: 345-349 |

29 | EE | Andrei Z. Broder, Martin E. Dyer, Alan M. Frieze, Prabhakar Raghavan, Eli Upfal: The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height. Inf. Process. Lett. 56(2): 79-81 (1995) |

28 | Martin E. Dyer, Trevor I. Fenner, Alan M. Frieze, Andrew Thomason: On Key Storage in Secure Networks. J. Cryptology 8(4): 189-200 (1995) | |

27 | Martin E. Dyer, Alan M. Frieze, Stephen Suen: Ordering Clone Libraries in Computational Biology. Journal of Computational Biology 2(2): 207-218 (1995) | |

26 | Jonathan Aronson, Martin E. Dyer, Alan M. Frieze, Stephen Suen: Randomized Greedy Matching II. Random Struct. Algorithms 6(1): 55-74 (1995) | |

1994 | ||

25 | Jonathan Aronson, Martin E. Dyer, Alan M. Frieze, Stephen Suen: On the Greedy Heuristic for Matchings. SODA 1994: 141-149 | |

24 | Martin E. Dyer, Alan M. Frieze, Mark Jerrum: Approximately Counting Hamilton Cycles in Dense Graphs. SODA 1994: 336-343 | |

23 | EE | Martin E. Dyer: On a Universal Chain Problem. Discrete Applied Mathematics 48(3): 219-229 (1994) |

22 | Martin E. Dyer, Alan M. Frieze: Random walks, totally unimodular matrices, and a randomised dual simplex algorithm. Math. Program. 64: 1-16 (1994) | |

1993 | ||

21 | Martin E. Dyer, Alan M. Frieze, Ravi Kannan, Ajai Kapoor, Ljubomir Perkovic, Umesh V. Vazirani: A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem. Combinatorics, Probability & Computing 2: 271-284 (1993) | |

1992 | ||

20 | Martin E. Dyer, Alan M. Frieze: Random Walks, Totally Unimodular Matrices and a Randomised Dual Simplex Algorithm. IPCO 1992: 72-84 | |

19 | EE | Martin E. Dyer: A Class of Convex Programs with Applications to Computational Geometry. Symposium on Computational Geometry 1992: 9-15 |

18 | Martin E. Dyer, Alan M. Frieze: Probabilistic analysis of the generalised assignment problem. Math. Program. 55: 169-181 (1992) | |

17 | Martin E. Dyer, Zoltán Füredi, Colin McDiarmid: Volumes Spanned by Random Points in the Hypercube. Random Struct. Algorithms 3(1): 91-106 (1992) | |

1991 | ||

16 | EE | Martin E. Dyer, Alan M. Frieze, Ravi Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies. J. ACM 38(1): 1-17 (1991) |

15 | Martin E. Dyer, Alan M. Frieze: Randomized Greedy Matching. Random Struct. Algorithms 2(1): 29-46 (1991) | |

14 | Martin E. Dyer, Alan M. Frieze: Probabilistic Analysis of a Parallel Algorithm for Finding the Lexicographically First Depth First Search Tree in a Dense Random Graph. Random Struct. Algorithms 2(2): 233-240 (1991) | |

13 | Martin E. Dyer: On Counting Lattice Points in Polyhedra. SIAM J. Comput. 20(4): 695-707 (1991) | |

1990 | ||

12 | Martin E. Dyer, Alan M. Frieze: Probabilistic Analysis of the Generalised Assignment Problem. IPCO 1990: 189-200 | |

11 | EE | Martin E. Dyer, Alan M. Frieze: On an optimization problem with nested constraints. Discrete Applied Mathematics 26(2-3): 159-173 (1990) |

10 | EE | Martin E. Dyer, Laurence A. Wolsey: Formulating the single machine sequencing problem with release dates as a mixed integer program. Discrete Applied Mathematics 26(2-3): 255-270 (1990) |

9 | Martin E. Dyer, Alan M. Frieze: On Patching Algorithms for Random Asymmetric Travelling Salesman Problems. Math. Program. 46: 361-378 (1990) | |

1989 | ||

8 | Martin E. Dyer, Alan M. Frieze, Ravi Kannan: A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies STOC 1989: 375-381 | |

7 | Martin E. Dyer, Alan M. Frieze: The Solution of Some Random NP-Hard Problems in Polynomial Expected Time. J. Algorithms 10(4): 451-489 (1989) | |

1988 | ||

6 | Martin E. Dyer, Alan M. Frieze: On the Complexity of Computing the Volume of a Polyhedron. SIAM J. Comput. 17(5): 967-974 (1988) | |

1986 | ||

5 | Martin E. Dyer, Alan M. Frieze: Fast Solution of Some Random NP-Hard Problems FOCS 1986: 331-336 | |

4 | Martin E. Dyer, Alan M. Frieze: Planar 3DM is NP-Complete. J. Algorithms 7(2): 174-184 (1986) | |

3 | Martin E. Dyer: On a Multidimensional Search Technique and its Application to the Euclidean One-Centre Problem. SIAM J. Comput. 15(3): 725-738 (1986) | |

1984 | ||

2 | Martin E. Dyer, Alan M. Frieze: A Partitioning Algorithm for Minimum Weighted Euclidean Matching. Inf. Process. Lett. 18(2): 59-62 (1984) | |

1 | Martin E. Dyer: Linear Time Algorithms for Two- and Three-Variable Linear Programs. SIAM J. Comput. 13(1): 31-45 (1984) |