| 2009 |
|---|
| 102 | EE | Martin E. Dyer,
Leslie Ann Goldberg,
Mark Jerrum:
The Complexity of Weighted Boolean CSP.
SIAM J. Comput. 38(5): 1970-1986 (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 | | 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) |
