Martin E. Dyer

According to our database1, Martin E. Dyer authored at least 129 papers between 1977 and 2018.

Collaborative distances:
  • Dijkstra number2 of four.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Other 

Links

Homepages:

On csauthors.net:

Bibliography

2018
Quasimonotone Graphs.
Proceedings of the Graph-Theoretic Concepts in Computer Science, 2018

2016
Counting 4×4 matrix partitions of graphs.
Discrete Applied Mathematics, 2016

On the switch Markov chain for perfect matchings.
Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2016

Discordant Voting Processes on Finite Graphs.
Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

2015
Erratum to: Computational complexity of stochastic programming problems.
Math. Program., 2015

On the chromatic number of a random hypergraph.
J. Comb. Theory, Ser. B, 2015

2014
A simple randomised algorithm for convex optimisation - Application to two-stage stochastic programming.
Math. Program., 2014

2013
An Effective Dichotomy for the Counting Constraint Satisfaction Problem.
SIAM J. Comput., 2013

The expressibility of functions on the boolean domain, with applications to counting CSPs.
J. ACM, 2013

The complexity of approximating conservative counting CSPs.
Proceedings of the 30th International Symposium on Theoretical Aspects of Computer Science, 2013

2012
The complexity of weighted and unweighted #CSP.
J. Comput. Syst. Sci., 2012

Log-supermodular functions, functional clones and counting CSPs.
Proceedings of the 29th International Symposium on Theoretical Aspects of Computer Science, 2012

2011
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241).
Dagstuhl Reports, 2011

The #CSP Dichotomy is Decidable.
Proceedings of the 28th International Symposium on Theoretical Aspects of Computer Science, 2011

Networks of random cycles.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Pairwise-Interaction Games.
Proceedings of the Automata, Languages and Programming - 38th International Colloquium, 2011

2010
Randomly coloring random graphs.
Random Struct. Algorithms, 2010

An approximation trichotomy for Boolean #CSP.
J. Comput. Syst. Sci., 2010

A Complexity Dichotomy For Hypergraph Partition Functions.
Computational Complexity, 2010

On the complexity of #CSP.
Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

The Complexity of Approximating Bounded-Degree Boolean #CSP.
Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

2009
The complexity of weighted Boolean #CSP with mixed signs.
Theor. Comput. Sci., 2009

The Complexity of Weighted Boolean #CSP.
SIAM J. Comput., 2009

The flip markov chain and a randomising P2P protocol.
Proceedings of the 28th Annual ACM Symposium on Principles of Distributed Computing, 2009

2008
Path coupling using stopping times and counting independent sets and colorings in hypergraphs.
Random Struct. Algorithms, 2008

08201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms.
Proceedings of the Design and Analysis of Randomized and Approximation Algorithms, 11.05., 2008

2007
Path coupling without contraction.
J. Discrete Algorithms, 2007

2006
Randomly coloring sparse random graphs with fewer colors than the maximum degree.
Random Struct. Algorithms, 2006

Computational complexity of stochastic programming problems.
Math. Program., 2006

On Counting Homomorphisms to Directed Acyclic Graphs.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Stopping Times, Metrics and Approximate Counting.
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Dobrushin Conditions and Systematic Scan.
Proceedings of the Approximation, 2006

2005
Metric Construction, Stopping Times and Path Coupling.
Electronic Colloquium on Computational Complexity (ECCC), 2005

On counting homomorphisms to directed acyclic graphs
Electronic Colloquium on Computational Complexity (ECCC), 2005

Dobrushin conditions and Systematic Scan
Electronic Colloquium on Computational Complexity (ECCC), 2005

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs
Electronic Colloquium on Computational Complexity (ECCC), 2005

Approximately counting integral flows and cell-bounded contingency tables.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Sampling regular graphs and a peer-to-peer network.
Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Path Coupling Using Stopping Times.
Proceedings of the Fundamentals of Computation Theory, 15th International Symposium, 2005

05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms.
Proceedings of the Design and Analysis of Randomized and Approximation Algorithms, 15.05., 2005

2004
Corrigendum: The complexity of counting graph homomorphisms.
Random Struct. Algorithms, 2004

Counting and sampling H-colourings?
Inf. Comput., 2004

Randomly coloring constant degree graphs
Electronic Colloquium on Computational Complexity (ECCC), 2004

The Relative Complexity of Approximate Counting Problems.
Algorithmica, 2004

Randomly Coloring Constant Degree Graphs.
Proceedings of the 45th Symposium on Foundations of Computer Science (FOCS 2004), 2004

2003
A probabilistic analysis of randomly generated binary constraint satisfaction problems.
Theor. Comput. Sci., 2003

Randomly coloring graphs with lower bounds on girth and maximum degree.
Random Struct. Algorithms, 2003

Approximate counting by dynamic programming.
Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

Random walks on the vertices of transportation polytopes with constant number of sources.
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2003

Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems.
Proceedings of the Discrete Mathematics and Theoretical Computer Science, 2003

2002
Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs.
Random Struct. Algorithms, 2002

Convergence Of The Iterated Prisoner's Dilemma Game.
Combinatorics, Probability & Computing, 2002

A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant.
Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Counting and Sampling H-Colourings.
Proceedings of the Randomization and Approximation Techniques, 6th International Workshop, 2002

Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows.
Proceedings of the 43rd Symposium on Foundations of Computer Science (FOCS 2002), 2002

2001
On Markov Chains for Randomly H-Coloring a Graph.
J. Algorithms, 2001

Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree.
Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs.
Proceedings of the Graphs, 2001

On the Sampling Problem for H-Colorings on the Hypercubic Lattice.
Proceedings of the Graphs, 2001

2000
Polynomial-time counting and sampling of two-rowed contingency tables.
Theor. Comput. Sci., 2000

Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems.
SIAM J. Comput., 2000

An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings.
SIAM J. Comput., 2000

The complexity of counting graph homomorphisms.
Random Struct. Algorithms, 2000

On Markov Chains for Independent Sets.
J. Algorithms, 2000

An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

The complexity of counting graph homomorphisms (extended abstract).
Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms, 2000

On the relative complexity of approximate counting problems.
Proceedings of the Approximation Algorithms for Combinatorial Optimization, 2000

1999
On Approximately Counting Colorings of Small Degree Graphs.
SIAM J. Comput., 1999

On Counting Independent Sets in Sparse Graphs.
Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998
On the Complexity of Computing Mixed Volumes.
SIAM J. Comput., 1998

Approximately Counting Hamilton Paths and Cycles in Dense Graphs.
SIAM J. Comput., 1998

A more rapidly mixing Markov chain for graph colorings.
Random Struct. Algorithms, 1998

An elementary analysis of a procedure for sampling points in a convex body.
Random Struct. Algorithms, 1998

Beating the 2 Delta Bound for Approximately Counting Colourings: A Computer-Assisted Proof of Rapid Mixing.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

Faster Random Generation of Linear Extensions.
Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998

A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables.
Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997
Sampling contingency tables.
Random Struct. Algorithms, 1997

On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension.
Math. Oper. Res., 1997

Graph Orientations with No Sink and an Approximation for a Hard Case of #SAT.
Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, 1997

Path Coupling: A Technique for Proving Rapid Mixing in Markov Chains.
Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997

1996
A Scalable Shared Queue on a Distributed Memory Machine.
Comput. J., 1996

Locating the Phase Transition in Binary Constraint Satisfaction Problems.
Artif. Intell., 1996

Implementation Issues Relating to the WPRAM Model for Scalable Computing.
Proceedings of the Euro-Par '96 Parallel Processing, 1996

1995
Randomized Greedy Matching II.
Random Struct. Algorithms, 1995

On Key Storage in Secure Networks.
J. Cryptology, 1995

Ordering Clone Libraries in Computational Biology.
Journal of Computational Biology, 1995

The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height.
Inf. Process. Lett., 1995

An Optimal Randomized Planar Convex Hull Algorithm With Good Empirical Performance.
Proceedings of the 7th Annual ACM Symposium on Parallel Algorithms and Architectures, 1995

A Parallel Algorithm for Linear Programming in Fixed Dimension.
Proceedings of the Eleventh Annual Symposium on Computational Geometry, 1995

1994
Random walks, totally unimodular matrices, and a randomised dual simplex algorithm.
Math. Program., 1994

The Probability of Unique Solutions of Sequencing by Hybridization.
Journal of Computational Biology, 1994

On a Universal Chain Problem.
Discrete Applied Mathematics, 1994

Approximately Counting Hamilton Cycles in Dense Graphs.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

On the Greedy Heuristic for Matchings.
Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms. 23-25 January 1994, 1994

1993
A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem.
Combinatorics, Probability & Computing, 1993

1992
Volumes Spanned by Random Points in the Hypercube.
Random Struct. Algorithms, 1992

Random Walks, Totally Unimodular Matrices and a Randomised Dual Simplex Algorithm.
Proceedings of the 2nd Integer Programming and Combinatorial Optimization Conference, 1992

A Class of Convex Programs with Applications to Computational Geometry.
Proceedings of the Eighth Annual Symposium on Computational Geometry, 1992

1991
On Counting Lattice Points in Polyhedra.
SIAM J. Comput., 1991

Probabilistic Analysis of a Parallel Algorithm for Finding the Lexicographically First Depth First Search Tree in a Dense Random Graph.
Random Struct. Algorithms, 1991

Randomized Greedy Matching.
Random Struct. Algorithms, 1991

A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies.
J. ACM, 1991

1990
On Patching Algorithms for Random Asymmetric Travelling Salesman Problems.
Math. Program., 1990

Formulating the single machine sequencing problem with release dates as a mixed integer program.
Discrete Applied Mathematics, 1990

On an optimization problem with nested constraints.
Discrete Applied Mathematics, 1990

Probabilistic Analysis of the Generalised Assignment Problem.
Proceedings of the 1st Integer Programming and Combinatorial Optimization Conference, 1990

Random Volumes in the n-Cube.
Proceedings of the Polyhedral Combinatorics, 1990

1989
A randomized algorithm for fixed-dimensional linear programming.
Math. Program., 1989

Probabilistic Analysis of the Multidimensional Knapsack Problem.
Math. Oper. Res., 1989

The Solution of Some Random NP-Hard Problems in Polynomial Expected Time.
J. Algorithms, 1989

A Random Polynomial Time Algorithm for Approximating the Volume of Convex Bodies
Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 1989

1988
On the Complexity of Computing the Volume of a Polyhedron.
SIAM J. Comput., 1988

1987
An algorithm for a separable integer programming problem with cumulatively bounded variables.
Discrete Applied Mathematics, 1987

1986
On a Multidimensional Search Technique and its Application to the Euclidean One-Centre Problem.
SIAM J. Comput., 1986

On linear programs with random costs.
Math. Program., 1986

Planar 3DM is NP-Complete.
J. Algorithms, 1986

Fast Solution of Some Random NP-Hard Problems
Proceedings of the 27th Annual Symposium on Foundations of Computer Science, 1986

1985
On the complexity of partitioning graphs into connected subgraphs.
Discrete Applied Mathematics, 1985

1984
Linear Time Algorithms for Two- and Three-Variable Linear Programs.
SIAM J. Comput., 1984

An O(n) algorithm for the multiple-choice knapsack linear program.
Math. Program., 1984

A Partitioning Algorithm for Minimum Weighted Euclidean Matching.
Inf. Process. Lett., 1984

1983
A note on bicriterion programming.
Math. Program., 1983

The Complexity of Vertex Enumeration Methods.
Math. Oper. Res., 1983

1982
Solving the subproblem in the lagrangian dual of separable discrete programs with linear constraints.
Math. Program., 1982

1980
Eliminating extraneous edges in Greenberg's algorithm.
Math. Program., 1980

Calculating surrogate constraints.
Math. Program., 1980

1977
An algorithm for determining all extreme points of a convex polytope.
Math. Program., 1977


  Loading...