Martin Dyer

Q: What Schools Are Affiliated With Martin Dyer

Martin Dyer is affiliated with the following schools: University of Leeds, Imperial College London, University of Oregon, University of California, Los Angeles

Martin Dyer's AcademicInfluence.com Rankings

Martin Dyer

Computer Science

#2090

World Rank

#2172

Historical Rank

Database

#4731

World Rank

#4914

Historical Rank

computer-science Degrees

Download Badge

Computer Science

Why Is Martin Dyer Influential?

(Suggest an Edit or Addition)

According to Wikipedia, Martin Edward Dyer is a professor in the School of Computing at the University of Leeds, Leeds, England. He graduated from the University of Leeds in 1967, obtained his MSc from Imperial College London in 1968 and his PhD from the University of Leeds in 1979. His research interests lie in theoretical computer science, discrete optimization and combinatorics. Currently, he focuses on the complexity of counting and the efficiency of Markov chain algorithms for approximate counting.

(See a Problem?)

Martin Dyer's Published Works

Number of citations in a given year to any of this author's works

Total number of citations to an author for the works they published in a given year. This highlights publication of the most important work(s) by the author

Published Works

A random polynomial-time algorithm for approximating the volume of convex bodies (1989) (790)
Path coupling: A technique for proving rapid mixing in Markov chains (1997) (379)
On the Complexity of Computing the Volume of a Polyhedron (1988) (340)
Locating the Phase Transition in Binary Constraint Satisfaction Problems (1996) (261)
Formulating the single machine sequencing problem with release dates as a mixed integer program (1990) (258)
Computational complexity of stochastic programming problems (2006) (254)
The complexity of counting graph homomorphisms (2000) (242)
Linear Time Algorithms for Two- and Three-Variable Linear Programs (1984) (219)
The Solution of Some Random NP-Hard Problems in Polynomial Expected Time (1989) (210)
Faster random generation of linear extensions (1999) (197)
A simple heuristic for the p-centre problem (1985) (181)
On counting independent sets in sparse graphs (1999) (178)
On a Multidimensional Search Technique and its Application to the Euclidean One-Centre Problem (1986) (178)
The Complexity of Vertex Enumeration Methods (1983) (167)
Computing the volume of convex bodies : a case where randomness provably helps (1991) (167)
On Markov Chains for Independent Sets (2000) (150)
Sampling regular graphs and a peer-to-peer network (2005) (149)
On the complexity of partitioning graphs into connected subgraphs (1985) (143)
Planar 3DM is NP-Complete (1986) (135)
On the relative complexity of approximate counting problems (2000) (135)
The Relative Complexity of Approximate Counting Problems (2000) (134)
On key storage in secure networks (1995) (126)
Sampling contingency tables (1997) (114)
Mixing in time and space for lattice spin systems: A combinatorial view (2002) (105)
Randomly coloring sparse random graphs with fewer colors than the maximum degree (2006) (101)
An algorithm for determining all extreme points of a convex polytope (1977) (99)
An O(n) algorithm for the multiple-choice knapsack linear program (1984) (97)
Calculating surrogate constraints (1980) (89)
The Complexity of Weighted Boolean #CSP (2007) (88)
Randomly coloring constant degree graphs (2004) (83)
On the Complexity of Computing Mixed Volumes (1998) (82)
An Effective Dichotomy for the Counting Constraint Satisfaction Problem (2010) (78)
On counting homomorphisms to directed acyclic graphs (2006) (77)
A more rapidly mixing Markov chain for graph colorings (1998) (72)
Randomized Greedy Matching (1991) (69)
Random walks, totally unimodular matrices, and a randomised dual simplex algorithm (1994) (67)
A class of convex programs with applications to computational geometry (1992) (67)
Markov chain comparison (2004) (63)
The Stable Marriage Problem: Structure and Algorithms (1991) (62)
An approximation trichotomy for Boolean #CSP (2007) (59)
On linear programs with random costs (1986) (58)
The Probability of Unique Solutions of Sequencing by Hybridization (1994) (57)
Randomly coloring graphs with lower bounds on girth and maximum degree (2003) (55)
Graph orientations with no sink and an approximation for a hard case of #SAT (1997) (54)
On Barvinok's Algorithm for Counting Lattice Points in Fixed Dimension (1997) (54)
A randomized algorithm for fixed-dimensional linear programming (1989) (53)
On Approximately Counting Colorings of Small Degree Graphs (1999) (53)
On the complexity of #CSP (2010) (52)
Randomized Greedy Matching II (1995) (51)
A Mildly Exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem (1993) (50)
A branch and bound algorithm for solving the multiple-choice knapsack problem (1984) (48)
A hybrid dynamic programming/branch-and-bound algorithm for the multiple-choice knapsack problem (1995) (46)
Rapidly mixing Markov chains for sampling contingency tables with a constant number of rows (2002) (46)
Surveys in Combinatorics, 1999: Random Walks on Combinatorial Objects (1999) (44)
Polynomial-time counting and sampling of two-rowed contingency tables (2000) (44)
Trees of homotopy types of two-dimensional CW-complexes (1973) (44)
The complexity of weighted and unweighted #CSP (2010) (43)
A polynomial-time algorithm to approximately count contingency tables when the number of rows is constant (2002) (43)
Approximate counting by dynamic programming (2003) (42)
An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings (2001) (41)
The expressibility of functions on the boolean domain, with applications to counting CSPs (2011) (40)
Beating the 2Δ bound for approximately counting colourings: a computer-assisted proof of rapid mixing (1998) (40)
Dobrushin Conditions and Systematic Scan (2006) (39)
Randomly colouring graphs with lower bounds on girth and maximum degree (2001) (39)
On the chromatic number of a random hypergraph (2012) (38)
The flip markov chain and a randomising P2P protocol (2009) (37)
The average performance of the greedy matching algorithm (1993) (36)
Matrix norms and rapid mixing for spin systems (2007) (36)
Volumes Spanned by Random Points in the Hypercube (1992) (36)
Probabilistic Analysis of the Multidimensional Knapsack Problem (1989) (36)
Approximately Counting Hamilton Paths and Cycles in Dense Graphs (1998) (34)
Mixing properties of the Swendsen–Wang process on the complete graph and narrow grids (2000) (34)
Fast solution of some random NP-hard problems (1986) (33)
Systematic scan for sampling colorings (2006) (33)
Analysis of heuristics for finding a maximum weight planar subgraph (1985) (31)
The Complexity of Weighted Boolean #CSP with Mixed Signs (2008) (31)
On the Switch Markov Chain for Perfect Matchings (2015) (29)
Stopping Times, Metrics and Approximate Counting (2006) (28)
Path coupling using stopping times and counting independent sets and colorings in hypergraphs (2005) (28)
Approximately counting Hamilton cycles in dense graphs (1994) (27)
On Markov Chains for Randomly H-Coloring a Graph (2001) (25)
The complexity of counting graph homomorphisms (extended abstract) (2000) (24)
A parallel algorithm for linear programming in fixed dimension (1995) (24)
Very rapid mixing of the Glauber dynamics for proper colorings on bounded‐degree graphs (2002) (24)
The complexity of approximating conservative counting CSPs (2012) (24)
On patching algorithms for random asymmetric travelling salesman problems (1990) (23)
Counting and sampling H-colourings? (2004) (23)
Probabilistic analysis of the generalised assignment problem (1990) (23)
Practical homomorphic encryption over the integers for secure computation in the cloud (2019) (23)
Convergence of the Iterated Prisoner's Dilemma Game (2002) (23)
Path Coupling, Dobrushin Uniqueness, and Approximate Counting (1997) (22)
Corrigendum: The complexity of counting graph homomorphisms (2004) (22)
An improved vertex enumeration algorithm (1982) (21)
Distinguishing arithmetic for certain stably isomorphic modules (1979) (21)
Parallel algorithm design on the WPRAM model (1995) (21)
A probabilistic analysis of randomly generated binary constraint satisfaction problems (2003) (21)
The Worst-Case Running Time of the Random Simplex Algorithm is Exponential in the Height (1995) (20)
The complexity of approximating bounded-degree Boolean #CSP (2010) (20)
Path coupling without contraction (2007) (20)
Random walks on the vertices of transportation polytopes with constant number of sources (2003) (19)
Structure and eigenvalues of heat-bath Markov chains (2013) (19)
An elementary analysis of a procedure for sampling points in a convex body (1998) (19)
Corrigendum: Sampling regular graphs and a peer-to-peer network (2012) (19)
The #CSP Dichotomy is Decidable (2011) (18)
Approximately counting integral flows and cell-bounded contingency tables (2005) (18)
Pairwise-Interaction Games (2011) (17)
On J. H. C. Whitehead's aspherical question I (1981) (17)
A Partitioning Algorithm for Minimum Weighted Euclidean Matching (1984) (15)
Discordant voting processes on finite graphs (2016) (14)
The flip Markov chain for connected regular graphs (2017) (14)
Linear programming in low dimensions (1997) (13)
A Complexity Dichotomy For Hypergraph Partition Functions (2008) (13)
Sampling hypergraphs with given degrees (2020) (13)
On the Strength of Connectivity of Random Subgraphs of the n-Cube (1987) (12)
Rapidly Mixing Markov Chains for Dismantleable Constraint Graphs (2002) (12)
Some #P-completeness Proofs for Colourings and Independent Sets (1997) (11)
Order-Preserving Encryption Using Approximate Integer Common Divisors (2017) (11)
A Scalable Shared Queue on a Distributed Memory Machine (1996) (10)
On an optimization problem with nested constraints (1990) (10)
Random Volumes in the n-Cube (1990) (9)
On the Sampling Problem for H-Colorings on the Hypercubic Lattice (2001) (9)
Practical Homomorphic Encryption Over the Integers (2017) (9)
On Counting Lattice Points in Polyhedra (1991) (9)
Log-supermodular functions, functional clones and counting CSPs (2011) (8)
A Genuinely Polynomial-Time Algorithms for Sampling Two-Rowed Contingency Tables (1998) (8)
Counting perfect matchings and the switch chain (2017) (8)
A simple randomised algorithm for convex optimisation (2014) (8)
Rational homology and Whitehead products. (1972) (8)
Partitioning heuristics for two geometric maximization problems (1984) (8)
16th ACM-SIAM Symposium on Discrete Algorithms (SODA 2005) (2002) (7)
Order-preserving encryption using approximate common divisors (2019) (7)
Randomly coloring random graphs (2010) (7)
Two-Dimensional Homotopy and Combinatorial Group Theory: Crossed Modules and Π2 Homotopy Modules (1993) (7)
Listing Vertices of Simple Polyhedra Associated with Dual LI(2) Systems (2003) (7)
On the second homotopy module of two-dimensional CW complexes (1976) (7)
Solving the subproblem in the lagrangian dual of separable discrete programs with linear constraints (1982) (7)
Scalable and portable computing using the WPRAM model (1997) (6)
An optimal randomized planar convex hull algorithm with good empirical performance (1995) (6)
Implementation Issues Relating to the WPRAM Model for Scalable Computing (1996) (6)
Correction to: “Rational homology and Whitehead products” (1977) (6)
An algorithm for a separable integer programming problem with cumulatively bounded variables (1987) (6)
Path Coupling Using Stopping Times (2005) (6)
On the 2-realizability of 2-types (1975) (5)
Trees of homotopy types of 2-dimensional complexes. II (1975) (5)
A topological interpretation for the bias invariant (1986) (5)
Homological Group Theory: Trees of homotopy types of ( m)-complexes (1979) (5)
Counting Independent Sets in Cocomparability Graphs (2018) (5)
An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract) (2000) (5)
The Iterated Prisoner's Dilemma on a Cycle (2011) (5)
A New Approach to Polynomial-Time Generation of Random Points in Convex Bodies (1996) (5)
Counting and Sampling H-Colourings (2002) (5)
Random Walks on Small World Networks (2017) (4)
Counting independent sets in graphs with bounded bipartite pathwidth (2018) (4)
Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs (2020) (4)
Nonminimal roots in homotopy trees. (1979) (4)
A Genuinely Polynomial-time Algorithm for Sampling Two-rowed Contingency Tables (extended Abstract) (1998) (4)
Two Term Conditions in π Exact Couples (1967) (3)
Eliminating extraneous edges in Greenberg's algorithm (1980) (3)
SUBCOMPLEXES OF TWO-COMPLEXES AND PROJECTIVE CROSSED MODULES (1987) (3)
Simple homotopy types for $(G,\,m)$-complexes (1981) (3)
Counting weighted independent sets beyond the permanent (2019) (3)
EULER CHARACTERISTICS OF GROUPS (1987) (3)
Erratum to: Computational complexity of stochastic programming problems (2015) (3)
A note on bicriterion programming (1983) (3)
Probabilistic Analysis of a Parallel Algorithm for Finding the Lexicographically First Depth First Search Tree in a Dense Random Graph (1991) (2)
Fast and Optimal Parallel Multidimensional Search in PRAMs with Applications to Linear Programming and Related Problems (2000) (2)
Homotopy trees with trivial classifying ring (1976) (2)
Coverings of mapping spaces (1969) (2)
Counting 4×4 Matrix Partitions of Graphs (2014) (2)
An application of homological algebra to the homotopy classification of two-dimensional CW-complexes (1980) (2)
Ordering Clone Libraries in Computational Biology (1995) (2)
Triangle-creation processes on cubic graphs (2019) (2)
The Complexity of Approximating Bounded-Degree Boolean \sharp CSP (2009) (1)
Groups with no infinite perfect subgroups and aspherical 2-complexes (1993) (1)
A Sub-exponential Time Algorithm for Approximating the Number of Solutions to a Multidimensional Knapsack Problem (1993) (1)
Projectivek-invariants (1976) (1)
On the Imitation Strategy for Games on Graphs (2011) (1)
Homotopy trees for periodic groups (1974) (1)
Graph classes and the switch Markov chain for matchings (2015) (1)
On Key Storage In Se ure Networks (1995) (1)
Linear programming (2018) (1)
A simple randomised algorithm for convex optimisation (2013) (1)
A triangle process on regular graphs (2020) (1)
On the greedy heuristic for matchings (1994) (1)
Metric Construction, Stopping Times and Path Coupling (2005) (1)
Quasimonotone graphs (2018) (1)
Homotopy trees: Essential height and roots (1976) (0)
The complexity of counting graph homomorphismsDRAFT : 1 April 1999 (1999) (0)
49 LINEAR PROGRAMMING (2017) (0)
Information Processing Letters running time of the random simplex algorithm is exponential in the height (1995) (0)
A triangle process on graphs with given degree sequence (2023) (0)
Randomly colouring random graphs (2008) (0)
Complexity of stochastic programming problems (1996) (0)
Networks of random cycles (2011) (0)
Corrigendum to Probability of Unique Solutions of Sequencing by Hybridization (1996) (0)
08201 – Abstract Collection Design and Analysis of Randomized and Approximation Algorithms — Dagstuhl Seminar — (2008) (0)
On a Universal Chain Problem (1994) (0)
RANDOM WALKS , TOTALLYUNIMODULAR MATRICES , AND ARANDOMISED DUAL SIMPLEXALGORITHM (2001) (0)
38 LINEAR PROGRAMMING (1997) (0)
A probabilisti analysis of randomly generated binary onstraint satisfa tion problems (2001) (0)
PR ] 1 4 O ct 2 00 4 Markov chain comparison ∗ (2006) (0)
Deducing strings from sub-string counts : a problem in computational biology (1993) (0)
50 LINEAR PROGRAMMING (2016) (0)
05201 Abstracts Collection - Design and Analysis of Randomized and Approximation Algorithms (2005) (0)
The expressibility of Boolean functions with applications to Counting CSPs (2011) (0)
Locating the phase transition in binary satisfaction problems (1996) (0)
PX and PXT: New Methods for Calculating Shoreline Change Rates (2007) (0)
Randomly oloring onstant degree graphs (2004) (0)
Subgroups with projective abelianization and trivial multiplicator (1984) (0)
olouring graphs with lower bounds on girth andmaximum degree (2003) (0)
On the cup product for groups (1992) (0)
The influence of $\pi_{1}(Y)$ on the homology of $M(X,Y)$ (1966) (0)
Design and Analysis of Randomized and Approximation Algorithms (Dagstuhl Seminar 11241) (2011) (0)
COUNTING WEIGHTED INDEPENDENT SETS BEYOND THE (2021) (0)
26 11241 – Design and Analysis of Randomized and Approximation Algorithms 2 Table of Contents Executive Summary (2011) (0)
Federer-Čech Couples (1969) (0)
Erratum to: Computational complexity of stochastic programming problems (2015) (0)

This paper list is powered by the following services:

Other Resources About Martin Dyer

en.wikipedia.org

What Schools Are Affiliated With Martin Dyer?

Martin Dyer is affiliated with the following schools: