Martin E. Dyer
According to our database^{1},
Martin E. Dyer
authored at least 129 papers
between 1977 and 2018.
Collaborative distances:
Collaborative distances:
Timeline
Legend:
Book In proceedings Article PhD thesis OtherLinks
Homepages:

at orcid.org

at dnb.info

at dl.acm.org
On csauthors.net:
Bibliography
2018
Quasimonotone Graphs.
Proceedings of the GraphTheoretic 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 TwentySeventh Annual ACMSIAM 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 twostage 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
Logsupermodular 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 TwentySecond Annual ACMSIAM Symposium on Discrete Algorithms, 2011
PairwiseInteraction 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 BoundedDegree 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 cellbounded contingency tables.
Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005
Sampling regular graphs and a peertopeer network.
Proceedings of the Sixteenth Annual ACMSIAM 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 Hcolourings?
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 ACMSIAM 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 boundeddegree graphs.
Random Struct. Algorithms, 2002
Convergence Of The Iterated Prisoner's Dilemma Game.
Combinatorics, Probability & Computing, 2002
A polynomialtime 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 HColourings.
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 HColoring 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 HColorings on the Hypercubic Lattice.
Proceedings of the Graphs, 2001
2000
Polynomialtime counting and sampling of tworowed 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 ACMSIAM Symposium on Discrete Algorithms, 2000
The complexity of counting graph homomorphisms (extended abstract).
Proceedings of the Eleventh Annual ACMSIAM 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 ComputerAssisted Proof of Rapid Mixing.
Proceedings of the Ninth Annual ACMSIAM Symposium on Discrete Algorithms, 1998
Faster Random Generation of Linear Extensions.
Proceedings of the Ninth Annual ACMSIAM Symposium on Discrete Algorithms, 1998
A Genuinely PolynomialTime Algorithms for Sampling TwoRowed 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 ACMSIAM 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 EuroPar '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 WorstCase 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 ACMSIAM Symposium on Discrete Algorithms. 2325 January 1994, 1994
On the Greedy Heuristic for Matchings.
Proceedings of the Fifth Annual ACMSIAM Symposium on Discrete Algorithms. 2325 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 nCube.
Proceedings of the Polyhedral Combinatorics, 1990
1989
A randomized algorithm for fixeddimensional linear programming.
Math. Program., 1989
Probabilistic Analysis of the Multidimensional Knapsack Problem.
Math. Oper. Res., 1989
The Solution of Some Random NPHard 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 OneCentre Problem.
SIAM J. Comput., 1986
On linear programs with random costs.
Math. Program., 1986
Planar 3DM is NPComplete.
J. Algorithms, 1986
Fast Solution of Some Random NPHard 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 ThreeVariable Linear Programs.
SIAM J. Comput., 1984
An O(n) algorithm for the multiplechoice 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