Skip to main content

Research Repository

Advanced Search

Professor Magnus Bordewich's Outputs (44)

Quantifying the difference between phylogenetic diversity and diversity indices (2024)
Journal Article
Bordewich, M., & Semple, C. (2024). Quantifying the difference between phylogenetic diversity and diversity indices. Journal of Mathematical Biology, 88(4), Article 40. https://doi.org/10.1007/s00285-024-02059-y

Phylogenetic diversity is a popular measure for quantifying the biodiversity of a collection Y of species, while phylogenetic diversity indices provide a way to apportion phylogenetic diversity to individual species. Typically, for some specific dive... Read More about Quantifying the difference between phylogenetic diversity and diversity indices.

On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks (2022)
Journal Article
Bordewich, M., Semple, C., & Wicke, K. (2022). On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks. Theoretical Computer Science, 917, 66-80. https://doi.org/10.1016/j.tcs.2022.03.012

Phylogenetic Diversity (PD) is a prominent quantitative measure of the biodiversity of a collection of present-day species (taxa). This measure is based on the evolutionary distance among the species in the collection. Loosely speaking, if T is a roo... Read More about On the Complexity of Optimising Variants of Phylogenetic Diversity on Phylogenetic Networks.

On the Maximum Agreement Subtree Conjecture for Balanced Trees (2022)
Journal Article
Bordewich, M., Linz, S., Owen, M., St. John, K., Semple, C., & Wicke, K. (2022). On the Maximum Agreement Subtree Conjecture for Balanced Trees. SIAM Journal on Discrete Mathematics, 36(1), 336-354. https://doi.org/10.1137/20m1379678

We give a counterexample to the conjecture of Martin and Thatte that two balanced rooted binary leaf-labelled trees on n leaves have a maximum agreement subtree (MAST) of size at least n 1 2 . In particular, we show that for any c > 0, there exist tw... Read More about On the Maximum Agreement Subtree Conjecture for Balanced Trees.

A universal tree-based network with the minimum number of reticulations (2018)
Journal Article
Bordewich, M., & Semple, C. (2018). A universal tree-based network with the minimum number of reticulations. Discrete Applied Mathematics, 250, 357-362. https://doi.org/10.1016/j.dam.2018.05.010

A tree-based network N on X is universal if every rooted binary phylogenetic X-tree is a base tree for N. Hayamizu and, independently, Zhang constructively showed that, for all positive integers n, there exists an universal tree-based network on n le... Read More about A universal tree-based network with the minimum number of reticulations.

Recovering normal networks from shortest inter-taxa distance information (2018)
Journal Article
Bordewich, M., Huber, K. T., Moulton, V., & Semple, C. (2018). Recovering normal networks from shortest inter-taxa distance information. Journal of Mathematical Biology, 77(3), 571-594. https://doi.org/10.1007/s00285-018-1218-x

Phylogenetic networks are a type of leaf-labelled, acyclic, directed graph used by biologists to represent the evolutionary history of species whose past includes reticulation events. A phylogenetic network is tree–child if each non-leaf vertex is th... Read More about Recovering normal networks from shortest inter-taxa distance information.

On the information content of discrete phylogenetic characters (2017)
Journal Article
Bordewich, M., Deutschmann, I. M., Fischer, M., Kasbohm, E., Semple, C., & Steel, M. (2018). On the information content of discrete phylogenetic characters. Journal of Mathematical Biology, 77(3), 527-544. https://doi.org/10.1007/s00285-017-1198-2

Phylogenetic inference aims to reconstruct the evolutionary relationships of different species based on genetic (or other) data. Discrete characters are a particular type of data, which contain information on how the species should be grouped togethe... Read More about On the information content of discrete phylogenetic characters.

Constructing Tree-Child Networks from Distance Matrices (2017)
Journal Article
Bordewich, M., Semple, C., & Tokac, N. (2017). Constructing Tree-Child Networks from Distance Matrices. Algorithmica, 80(8), 2240-2259. https://doi.org/10.1007/s00453-017-0320-6

A tree-child network is a phylogenetic network with the property that each non-leaf vertex is the parent of a tree vertex or a leaf. In this paper, we show that a tree-child network on taxa (leaf) set X with an outgroup and a positive real-valued wei... Read More about Constructing Tree-Child Networks from Distance Matrices.

Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks (2017)
Journal Article
Bordewich, M., Linz, S., & Semple, C. (2017). Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks. Journal of Theoretical Biology, 423, 1-12. https://doi.org/10.1016/j.jtbi.2017.03.032

Over the last fifteen years, phylogenetic networks have become a popular tool to analyse relationships between species whose past includes reticulation events such as hybridisation or horizontal gene transfer. However, the space of phylogenetic netwo... Read More about Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks.

An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances (2016)
Journal Article
Bordewich, M., & Tokac, N. (2016). An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances. Discrete Applied Mathematics, 213, 47-59. https://doi.org/10.1016/j.dam.2016.05.011

Traditional “distance based methods” reconstruct a phylogenetic tree from a matrix of pair-wise distances between taxa. A phylogenetic network is a generalisation of a phylogenetic tree that can describe evolutionary events such as reticulation and h... Read More about An algorithm for reconstructing ultrametric tree-child networks from inter-taxa distances.

On the Fixed Parameter Tractability of Agreement-based Phylogenetic Distances (2016)
Journal Article
Bordewich, M., Scornavacca, C., Tokac, N., & Weller, M. (2017). On the Fixed Parameter Tractability of Agreement-based Phylogenetic Distances. Journal of Mathematical Biology, 74(1), 239-257. https://doi.org/10.1007/s00285-016-1023-3

Three important and related measures for summarizing the dissimilarity in phylogenetic trees are the minimum number of hybridization events required to fit two phylogenetic trees onto a single phylogenetic network (the hybridization number), the (roo... Read More about On the Fixed Parameter Tractability of Agreement-based Phylogenetic Distances.

Reticulation-Visible Networks (2016)
Journal Article
Bordewich, M., & Semple, C. (2016). Reticulation-Visible Networks. Advances in Applied Mathematics, 78, 114-141. https://doi.org/10.1016/j.aam.2016.04.004

Let X be a finite set, N be a reticulation-visible network on X , and T be a rooted binary phylogenetic tree. We show that there is a polynomial-time algorithm for deciding whether or not N displays T. Furthermore, for all |X|≥1, we show that N has a... Read More about Reticulation-Visible Networks.

Determining phylogenetic networks from inter-taxa distances (2015)
Journal Article
Bordewich, M., & Semple, C. (2016). Determining phylogenetic networks from inter-taxa distances. Journal of Mathematical Biology, 73(2), 283-303. https://doi.org/10.1007/s00285-015-0950-8

We consider the problem of determining the topological structure of a phylogenetic network given only information about the path-length distances between taxa. In particular, one of the main results of the paper shows that binary tree-child networks... Read More about Determining phylogenetic networks from inter-taxa distances.

Defining a Phylogenetic Tree with the Minimum Number of r-State Characters (2015)
Journal Article
Bordewich, M., & Semple, C. (2015). Defining a Phylogenetic Tree with the Minimum Number of r-State Characters. SIAM Journal on Discrete Mathematics, 29(2), 835-853. https://doi.org/10.1137/130924469

Semple and Steel (2002) showed that if T is a phylogenetic X-tree and C is a collection of r-state characters that defines T , then |C| ≥ (n − 3)/(r − 1), where n = |X|. In this paper, we show that, provided n is sufficiently large, this lower bound... Read More about Defining a Phylogenetic Tree with the Minimum Number of r-State Characters.

Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width (2014)
Journal Article
Bordewich, M., & Kang, R. (2014). Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width. Electronic Journal of Combinatorics, 21(4), Article 19

Motivated by the `subgraphs world' view of the ferromagnetic Ising model, we analyse the mixing times of Glauber dynamics based on subset expansion expressions for classes of graph, hypergraph and matroid polynomials. With a canonical paths argument,... Read More about Subset Glauber Dynamics on Graphs, Hypergraphs and Matroids of Bounded Tree-Width.

Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model (2014)
Journal Article
Bordewich, M., Greenhill, C., & Patel, V. (2016). Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model. Random Structures and Algorithms, 48(1), 21-52. https://doi.org/10.1002/rsa.20569

We present several results on the mixing time of the Glauber dynamics for sampling from the Gibbs distribution in the ferromagnetic Potts model. At a fixed temperature and interaction strength, we study the interplay between the maximum degree (Δ) of... Read More about Mixing of the Glauber Dynamics for the Ferromagnetic Potts Model.

Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution (2013)
Journal Article
Bordewich, M., & Mihaescu, R. (2013). Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 10(3), 576-583. https://doi.org/10.1109/tcbb.2013.39

Distance-based phylogenetic methods attempt to reconstruct an accurate phylogenetic tree from an estimated matrix of pairwise distances between taxa. This paper examines two distance-based algorithms (GREEDYBME and FASTME) that are based on the princ... Read More about Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution.

Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems (2012)
Journal Article
Bordewich, M., & Semple, C. (2012). Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems. Journal of Mathematical Biology, 64(1), 69-85. https://doi.org/10.1007/s00285-011-0405-9

Arising in the context of biodiversity conservation, the Budgeted Nature Reserve Selection (BNRS) problem is to select, subject to budgetary constraints, a set of regions to conserve so that the phylogenetic diversity (PD) of the set of species conta... Read More about Budgeted Nature Reserve Selection with diversity feature loss and arbitrary split systems.

Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width (2011)
Book Chapter
Bordewich, M., & Kang, R. (2011). Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width. In L. Aceto, M. Henzinger, & J. Sgall (Eds.), Automata, languages and programming (533-544). Springer Verlag. https://doi.org/10.1007/978-3-642-22006-7_45

Motivated by the ‘subgraphs world’ view of the ferromagnetic Ising model, we develop a general approach to studying mixing times of Glauber dynamics based on subset expansion expressions for a class of graph polynomials. With a canonical paths argume... Read More about Rapid Mixing of Subset Glauber Dynamics on Graphs of Bounded Tree-Width.

A Network Approach to Study Karyotypic Evolution: The Chromosomal Races of the Common Shrew (Sorex araneus) and House Mouse (Mus musculus) as Model Systems (2010)
Journal Article
White, T. A., Bordewich, M., & Searle, J. B. (2010). A Network Approach to Study Karyotypic Evolution: The Chromosomal Races of the Common Shrew (Sorex araneus) and House Mouse (Mus musculus) as Model Systems. Systematic Biology, 59(3), 262-276. https://doi.org/10.1093/sysbio/syq004

The development of methods to reconstruct phylogenies from karyotypic data has lagged behind what has been achieved with molecular and morphological characters. This hampers our understanding of the role of chromosomal rearrangements in speciation, w... Read More about A Network Approach to Study Karyotypic Evolution: The Chromosomal Races of the Common Shrew (Sorex araneus) and House Mouse (Mus musculus) as Model Systems.

Optimizing phylogenetic diversity across two trees (2009)
Journal Article
Bordewich, M., Semple, C., & Spillner, A. (2009). Optimizing phylogenetic diversity across two trees. Applied Mathematics Letters, 22(5), 638-641. https://doi.org/10.1016/j.aml.2008.05.004

We present a polynomial-time algorithm for finding an optimal set of taxa that maximizes the weighted sum of the phylogenetic diversity across two phylogenetic trees. This resolves one of the challenges proposed as part of the Phylogenetics Programme... Read More about Optimizing phylogenetic diversity across two trees.

Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference (2009)
Journal Article
Bordewich, M., Gascuel, O., Huber, K., & Moulton, V. (2009). Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(1), 110-117. https://doi.org/10.1109/tcbb.2008.37

Many phylogenetic algorithms search the space of possible trees using topological rearrangements and some optimality criterion. FastME is such an approach that uses the balanced minimum evolution (BME) principle, which computer studies have demonstra... Read More about Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference.

Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution (2008)
Journal Article
Bordewich, M., Rodrigo, A., & Semple, C. (2008). Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution. Systematic Biology, 57(6), 825-834. https://doi.org/10.1080/10635150802552831

Three desirable properties for any method of selecting a subset of evolutionary units (EUs) for conservation or for genomic sequencing are discussed. These properties are spread, stability, and applicability. We are motivated by a practical case in w... Read More about Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution.

A 3-approximation algorithm for the subtree distance between phylogenies (2008)
Journal Article
Bordewich, M., McCartin, C., & Semple, C. (2008). A 3-approximation algorithm for the subtree distance between phylogenies. Journal of discrete algorithms, 6(3), 458-471. https://doi.org/10.1016/j.jda.2007.10.002

In this paper, we give a (polynomial-time) 3-approximation algorithm for the rooted subtree prune and regraft distance between two phylogenetic trees. This problem is known to be NP-complete and the best previously known approximation algorithm is a... Read More about A 3-approximation algorithm for the subtree distance between phylogenies.

Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs (2008)
Journal Article
Bordewich, M., Karpinski, M., & Dyer, M. (2008). Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs. Random Structures and Algorithms, 32(3), 375-399. https://doi.org/10.1002/rsa.20204

We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree... Read More about Path Coupling Using Stopping Times and Counting Independent Sets and Colourings in Hypergraphs.

Nature Reserve Selection Problem: A Tight Approximation Algorithm (2008)
Journal Article
Bordewich, M., & Semple, C. (2008). Nature Reserve Selection Problem: A Tight Approximation Algorithm. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 5(2), 275-280. https://doi.org/10.1109/tcbb.2007.70252

The nature reserve selection problem is a problem that arises in the context of studying biodiversity conservation. Subject to budgetary constraints, the problem is to select a set of regions to be conserved so that the phylogenetic diversity of the... Read More about Nature Reserve Selection Problem: A Tight Approximation Algorithm.

Computing the hybridisation number of two phylogenetic trees is fixed parameter tractable (2007)
Journal Article
Bordewich, M., & Semple, C. (2007). Computing the hybridisation number of two phylogenetic trees is fixed parameter tractable. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 4(3), 458-466. https://doi.org/10.1109/tcbb.2007.1019

Reticulation processes in evolution mean that the ancestral history of certain groups of present-day species is non-tree-like. These processes include hybridization, lateral gene transfer, and recombination. Despite the existence of reticulation, suc... Read More about Computing the hybridisation number of two phylogenetic trees is fixed parameter tractable.

A Reduction Algorithm for Computing the Hybridization Number of Two Trees (2007)
Journal Article
Bordewich, M., Linz, S., St. John, K., & Semple, C. (2007). A Reduction Algorithm for Computing the Hybridization Number of Two Trees. Evolutionary Bioinformatics, 3, 86-98

Hybridization is an important evolutionary process for many groups of species. Thus, conflicting signals in a data set may not be the result of sampling or modeling errors, but due to the fact that hybridization has played a significant role in the e... Read More about A Reduction Algorithm for Computing the Hybridization Number of Two Trees.

Computing the minimum number of hybridisation events for a consistent evolutionary history (2007)
Journal Article
Bordewich, M., & Semple, C. (2007). Computing the minimum number of hybridisation events for a consistent evolutionary history. Discrete Applied Mathematics, 155(8), 914-928. https://doi.org/10.1016/j.dam.2006.08.008

It is now well-documented that the structure of evolutionary relationships between a set of present-day species is not necessarily tree-like. The reason for this is that reticulation events such as hybridizations mean that species are a mixture of ge... Read More about Computing the minimum number of hybridisation events for a consistent evolutionary history.

Identifying X-Trees with Few Characters (2006)
Journal Article
Bordewich, M., Semple, C., & Steel, M. (2006). Identifying X-Trees with Few Characters. Electronic Journal of Combinatorics, 13(1),

Previous work has shown the perhaps surprising result that, for any binary phylogenetic tree T, there is a set of four characters that define T. Here we deal with the general case, where T is an arbitrary X-tree. We show that if d is the maximum degr... Read More about Identifying X-Trees with Few Characters.

Extending the limits of supertree methods (2006)
Journal Article
Bordewich, M., Evans, G., & Semple, C. (2006). Extending the limits of supertree methods. Annals of Combinatorics, 10, 31-51

Recently, two exact polynomial-time supertree methods have been developed in which the traditional input of rooted leaf-labelled trees has been extended in two separate ways. The first method, called RANKEDTREE, allows for the inclusion of relative d... Read More about Extending the limits of supertree methods.

Approximate counting and quantum computation (2005)
Journal Article
Bordewich, M., Freedman, M., Lovasz, L., & Welsh, D. (2005). Approximate counting and quantum computation. Combinatorics, Probability and Computing, 14(5-6), 737-754. https://doi.org/10.1017/s0963548305007005

Motivated by the result that an `approximate' evaluation of the Jones polynomial of a braid at a $5^{th}$ root of unity can be used to simulate the quantum part of any algorithm in the quantum complexity class BQP, and results relating BQP to the cou... Read More about Approximate counting and quantum computation.

Identifying phylogenetic trees (2005)
Journal Article
Bordewich, M., Huber, K., & Semple, C. (2005). Identifying phylogenetic trees. Discrete Mathematics, 300(1-3), 30-43. https://doi.org/10.1016/j.disc.2005.06.015

A central problem that arises in evolutionary biology is that of displaying partitions of subsets of a finite set X on a tree whose vertices are partially labelled with the elements of X. Such a tree is called an X-tree and, for a collection C of par... Read More about Identifying phylogenetic trees.

On the computational complexity of the rooted subtree prune and regraft distance (2005)
Journal Article
Bordewich, M., & Semple, C. (2005). On the computational complexity of the rooted subtree prune and regraft distance. Annals of Combinatorics, 8(4), 409-423. https://doi.org/10.1007/s00026-004-0229-z

The graph-theoretic operation of rooted subtree prune and regraft is increasingly being used as a tool for understanding and modelling reticulation events in evolutionary biology. In this paper, we show that computing the rooted subtree prune and reg... Read More about On the computational complexity of the rooted subtree prune and regraft distance.

Counting Consistent Phylogenetic Trees is #P-complete (2004)
Journal Article
Bordewich, M., Semple, C., & Talbot, J. (2004). Counting Consistent Phylogenetic Trees is #P-complete. Advances in Mathematics, 33(2), 416-430. https://doi.org/10.1016/j.aam.2003.08.006

Reconstructing phylogenetic trees is a fundamental task in evolutionary biology. Various algorithms exist for this purpose, many of which come under the heading of `supertree methods'. These methods amalgamate a collection Ρ of phylogenetic trees int... Read More about Counting Consistent Phylogenetic Trees is #P-complete.

Approximating the number of acyclic orientations for a class of sparse graphs (2004)
Journal Article
Bordewich, M. (2004). Approximating the number of acyclic orientations for a class of sparse graphs. Combinatorics, Probability and Computing, 13(1), 1-16. https://doi.org/10.1017/s0963548303005844

The Tutte polynomial $T(G;x,y)$ of a graph evaluates to many interesting combinatorial quantities at various points in the $(x,y)$ plane, including the number of spanning trees, number of forests, number of acyclic orientations, the reliability polyn... Read More about Approximating the number of acyclic orientations for a class of sparse graphs.

Evaluating Gaussian Grasp Maps for Generative Grasping Models
Presentation / Conference Contribution
Prew, W., Breckon, T., Bordewich, M., & Beierholm, U. (2022, July). Evaluating Gaussian Grasp Maps for Generative Grasping Models. Presented at Proc. Int. Joint Conf. Neural Networks, Padova, Italy

Generalising robotic grasping to previously unseen objects is a key task in general robotic manipulation. The current method for training many antipodal generative grasping models rely on a binary ground truth grasp map generated from the centre thir... Read More about Evaluating Gaussian Grasp Maps for Generative Grasping Models.

Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss
Presentation / Conference Contribution
Prew, W., Breckon, T., Bordewich, M., & Beierholm, U. (2021, January). Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss. Presented at 25th International Conference on Pattern Recognition (ICPR 2020), Milan, Italy

In this paper we introduce two methods of improving real-time object grasping performance from monocular colour images in an end-to-end CNN architecture. The first is the addition of an auxiliary task during model training (multi-task learning). Our... Read More about Improving Robotic Grasping on Monocular Images Via Multi-Task Learning and Positional Loss.

Autoencoders Without Reconstruction for Textural Anomaly Detection
Presentation / Conference Contribution
Adey, P., Akcay, S., Bordewich, M., & Breckon, T. (2021, July). Autoencoders Without Reconstruction for Textural Anomaly Detection. Presented at 2021 International Joint Conference on Neural Networks (IJCNN), Shenzhen, China

Automatic anomaly detection in natural textures is a key component within quality control for a range of high-speed, high-yield manufacturing industries that rely on camera-based visual inspection techniques. Targeting anomaly detection through the u... Read More about Autoencoders Without Reconstruction for Textural Anomaly Detection.

On the approximation complexity hierarchy.
Presentation / Conference Contribution
Bordewich, M. (2010, September). On the approximation complexity hierarchy. Presented at 8th International Workshop on International Workshop on Approximation and Online Algorithms, WAOA 2010, Liverpool

This paper presents an extension of Ladner’s Theorem to the approximation complexity hierarchy. In 1975 Ladner proved that if P≠NP, then there exists an incomplete problem A which is neither in P nor NP-complete. Here we show that if RP≠NP, then ther... Read More about On the approximation complexity hierarchy..

Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution.
Presentation / Conference Contribution
Bordewich, M., & Mihaescu, R. (2010, September). Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution. Presented at 10th Workshop on Algorithms in Bioinformatics (WABI 2010), Liverpool

Distance based phylogenetic methods attempt to reconstruct an accurate phylogenetic tree relating a given set of taxa from an estimated matrix of pair-wise distances between taxa. This paper examines two distance based algorithms (GreedyBME and FastM... Read More about Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution..

Path coupling using stopping times
Presentation / Conference Contribution
Bordewich, M., Dyer, M., & Karpinski, M. (2005, August). Path coupling using stopping times. Presented at 15th International Symposium Fundamentals of Computation Theory : FCT 2005., Lubeck, Germany

We analyse the mixing time of Markov chains using path coupling with stopping times. We apply this approach to two hypergraph problems. We show that the Glauber dynamics for independent sets in a hypergraph mixes rapidly as long as the maximum degree... Read More about Path coupling using stopping times.

Stopping times, metrics and approximate counting
Presentation / Conference Contribution
Bordewich, M., Dyer, M., & Karpinski, M. (2006, July). Stopping times, metrics and approximate counting. Presented at 33rd International Colloquium of Automata, Languages and Programming (ICALP 2006)., Venice, Italy

In this paper we examine the importance of the choice of metric in path coupling, and its relationship to stopping time analysis. We give strong evidence that stopping time analysis is no more powerful than standard path coupling. In particular, we p... Read More about Stopping times, metrics and approximate counting.