Search filters

List of works by Martin Dyer

A Complexity Dichotomy For Hypergraph Partition Functions

A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem

A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant

article by Mary Cryan & Martin Dyer published September 2003 in Journal of Computer and System Sciences

A probabilistic analysis of randomly generated binary constraint satisfaction problems

A random polynomial-time algorithm for approximating the volume of convex bodies

article by Martin Dyer et al published 3 January 1991 in Journal of the ACM

A simple randomised algorithm for convex optimisation

article by Martin Dyer et al published 13 October 2013 in Mathematical Programming

An Effective Dichotomy for the Counting Constraint Satisfaction Problem

An algorithm for a separable integer programming problem with cumulatively bounded variables

An approximation trichotomy for Boolean #CSP

Approximately Counting Hamilton Paths and Cycles in Dense Graphs

Approximately Counting Integral Flows and Cell-Bounded Contingency Tables

article by Mary Cryan et al published January 2010 in SIAM Journal on Computing

Approximately counting integral flows and cell-bounded contingency tables

scholarly article published 2005

Computational complexity of stochastic programming problems

Convergence of the Iterated Prisoner's Dilemma Game

Corrigendum: The complexity of counting graph homomorphisms

scholarly article by Martin Dyer & Catherine Greenhill published 2004 in Random Structures and Algorithms

Counting 4 × 4 matrix partitions of graphs

Counting and Sampling H-Colourings

Counting and sampling H-colourings

Counting independent sets in cocomparability graphs

scholarly article by Martin Dyer & Haiko Müller published April 2019 in Information Processing Letters

Discordant Voting Processes on Finite Graphs

Dobrushin Conditions and Systematic Scan

Erratum to: Computational complexity of stochastic programming problems

scholarly article published in Mathematical Programming

Faster random generation of linear extensions

scientific article (publication date: April 1999)

Graph classes and the switch Markov chain for matchings

Markov chain comparison

Matrix norms and rapid mixing for spin systems

Mixing in Time and Space for Lattice Spin Systems: A Combinatorial View

Mixing in time and space for lattice spin systems: A combinatorial view

scholarly article by Martin Dyer et al published 2004 in Random Structures and Algorithms

On Counting Homomorphisms to Directed Acyclic Graphs

On Counting Independent Sets in Sparse Graphs

On Markov Chains for Independent Sets

On Markov Chains for Randomly H-Coloring a Graph

On a universal chain problem

On counting homomorphisms to directed acyclic graphs

On key storage in secure networks

scholarly article by Martin Dyer et al published 1995 in Journal of Cryptology

On the Complexity of Computing the Volume of a Polyhedron

article by Martin Dyer & Alan M. Frieze published October 1988 in SIAM Journal on Computing

On the Switch Markov Chain for Perfect Matchings

On the chromatic number of a random hypergraph

On the switch Markov chain for perfect matchings

Order-Preserving Encryption Using Approximate Integer Common Divisors

Pairwise-Interaction Games

Path coupling using stopping times and counting independent sets and colorings in hypergraphs

scholarly article by Magnus Bordewich et al published 2008 in Random Structures and Algorithms

Path coupling without contraction

Path coupling: A technique for proving rapid mixing in Markov chains

article

Practical Homomorphic Encryption Over the Integers for Secure Computation in the Cloud

Probabilistic analysis of a parallel algorithm for finding the lexicographically first depth first search tree in a dense random graph

article by Martin Dyer & Alan Friezet published 5 July 2007 in Random Structures and Algorithms

Probabilistic analysis of the generalised assignment problem

Quasimonotone Graphs

Random walks on the vertices of transportation polytopes with constant number of sources

scholarly article by Mary Cryan et al published October 2008 in Random Structures and Algorithms

Random walks, totally unimodular matrices, and a randomised dual simplex algorithm

Randomized greedy matching

Randomized greedy matching. II

scholarly article by Jonathan Aronson et al published January 1995 in Random Structures and Algorithms

Randomly coloring constant degree graphs

scholarly article by Martin Dyer et al published 3 August 2012 in Random Structures and Algorithms

Randomly coloring graphs with lower bounds on girth and maximum degree

scholarly article by Martin Dyer & Alan M. Frieze published 1 August 2003 in Random Structures and Algorithms

Randomly coloring random graphs

Randomly coloring sparse random graphs with fewer colors than the maximum degree

scholarly article by Martin Dyer et al published 2006 in Random Structures and Algorithms

Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs

Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows

article by Mary Cryan et al published January 2006 in SIAM Journal on Computing

Sampling Regular Graphs and a Peer-to-Peer Network

article published in 2006

Stopping Times, Metrics and Approximate Counting

Structure and eigenvalues of heat-bath Markov chains

Systematic scan for sampling colorings

article published in 2006

The Complexity of Weighted Boolean #CSP

The Relative Complexity of Approximate Counting Problems

The complexity of approximating bounded-degree Boolean #CSP

The complexity of approximating conservative counting CSPs

article published in 2015

The complexity of weighted Boolean #CSP with mixed signs

The complexity of weighted and unweighted #CSP

The expressibility of functions on the boolean domain, with applications to counting CSPs

The flip markov chain and a randomising P2P protocol

The probability of unique solutions of sequencing by hybridization

scientific article published in January 1994

Very rapid mixing of the Glauber dynamics for proper colorings on bounded-degree graphs

article