Dr Magnus Bordewich

Magnus Bordewich
MMath DPhil FHEA
Senior lecturer at Durham University

School of Engineering and Computing Sciences
University of Durham
Science Laboratories
South Road
Durham
DH1 3LE
Tel. +44 (0) 191 3342329
Email:

I am a member of the Algorithms and Complexity research group.

EPSRC Grant: Approximation and mixing times in the ferromagnetic Potts model
This grant is to undertake research on algorithms and approximation methods relating to the ferromagnetic Potts model. In particular, we will focus on Markov chain Monte Carlo techniques, the mixing time of Glauber dynamics and the approximability of the partition function of the Potts model. We will be building on recent research on Markov chain Monte Carlo mixing times in the anti-ferromagnetic Potts model, including Markov chains of proper graph colourings. We will explore extensions to other H-colouring problems in graph theory.

In January 2010 I was joined by Ross Kang, Post-doctoral Research Associate, who is working on this project with me. A paper containing our first results, related to the mixing time of a Markov chain subgraphs, has been submitted and is available below. From November 2011 Viresh Patel has taken over as PDRA on this project.

EPSRC Postdoctoral fellowship:
Between September 2006 and September 2009 I held an EPSRC postdoctoral fellowship, in order to conduct research into "Randomised algorithms and approximation in phylogenetics". Details of the research and places I went to during this period can be found on the fellowship pages.

Research:
Discrete mathematics, theoretical computer science and applications in phylogenetics.

Previous posts:

Post-doc: School of Computer Science, University of Leeds, U.K.

Post-doc: Biomathematics Research Centre at the

Department of Mathematics and Statistics, University of Canterbury, New Zealand.

MMath, D.Phil: Department of Mathematics, University of Oxford, U.K.

Selected Publications:
If you are interested in any of the preprints or articles in press, please get in touch with me and I will be happy to discuss them.

Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width. Abstract.
Bordewich, M. and Kang, R. In Press, 2011.

On the approximation complexity hierarchy. Abstract.
Bordewich, M.. In K. Jansen and R. Solis-Oba, editors, Proceedings of WAOA 2010, 8th Workshop on Approximation and Online Algorithms, LNCS. Springer-Verlag, 2010.

Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution. Abstract.
Bordewich, M. and Mihaescu, R., In V. Moulton and M. Singh, editors, Proceedings of WABI 2010, 10th International Workshop on Algorithms in Bioinformatics, volume 6293 of LNBI, pages 250-261. Springer-Verlag, 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. Abstract.
White, T. A., Bordewich, M. and Searle, J. B., Systematic Biology, 59(3):262-276 (2010).

Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference. Abstract.
Bordewich, M., Gascuel, O., Huber, K. T. and Moulton, V., Transactions on Computational Biology and Bioinformatics, 6(1):110-117 (2009).

Optimizing phylogenetic diversity across two trees. Abstract.
Bordewich, M., Semple, C. and Spillner, A., Applied Mathematics Letters. 22(5):638-641 (2009).

Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution. Abstract.
Bordewich, M., Rodrigo, A. G. and Semple, C., Systematic Biology, 57(6):825-834 (2008).

A 3-approximation algorithm for the subtree distance between phylogenies. Abstract.
Bordewich, M., McCartin, C. and Semple, C., Journal of Discrete Algorithms, 6(3):458-471 (2008).

Nature Reserve Selection Problem: A Tight Approximation Algorithm. Abstract.
Bordewich, M., Semple, C., Transactions on Computational Biology and Bioinformatics, 5(2) (2008).

Path coupling using stopping times and counting independent sets and colourings in hypergraphs. Abstract.
Bordewich, M., Dyer, M. and Karpinski, M., Random Structures and Algorithms 32(3):375-399 (2008).

Optimizing phylogenetic diversity across two trees. Abstract.
Bordewich, M., Semple, C. and Spillner, A., Isaac Newton Institute Preprint Series. NI07068-PLG (2007).

A Reduction Algorithm for Computing the Hybridization Number of Two Trees. Abstract.
Bordewich, M., Linz, S., St. John, K. and Semple, C., Evolutionary bioinformatics, 3:86-98 (2007).

Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable Abstract.
Bordewich, M., Semple, C., Transactions on Computational Biology and Bioinformatics,, 4(3):458-466 (2007).

Path coupling without contraction. Abstract.
Bordewich, M. and Dyer, M., Journal of Discrete Algorithms, 5:280-292 (2007).

Computing the minimum number of hybridisation events for a consistent evolutionary history. Abstract.
Bordewich, M., Semple, C., Discrete Applied Mathematics, 155(8):914-928 (2007).

Stopping times, metrics and approximate counting. Abstract.
Bordewich, M., Dyer, M. and Karpinski, M., In proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), LNCS 4051:108-119, Springer-Verlag.

Identifying X-trees with few characters. Abstract.
Bordewich, M., Semple, C., and Steel, M. The Electronic Journal of Combinatorics, 13 (2006).

Extending the limits of supertree methods. Abstract.
Bordewich, M., Evans, G. and Semple, C., Annals of Combinatorics, 10:31-51 (2006).

Path coupling using stopping times. Abstract.
Bordewich, M., Dyer, M. and Karpinski, M., In proceedings of Fundamentals of Computation Theory (FCT 2005), LNCS 3623:19-31, Springer-Verlag.

Identifying phylogenetic trees. Abstract.
Bordewich, M., Semple, C., and Huber, K., Discrete Mathematics, 300(1-3):30-43 (2005).

Approximate counting and quantum computation. Abstract.
Bordewich, M., Freedman, M., Lovász, L. and Welsh, D., Combinatorics, Probability and Computing, 14(5-6):737-754 (2005).

On the computational complexity of the rooted subtree prune and regraft distance. Abstract.
Bordewich, M., Semple, C., Annals of Combinatorics, 8(4):409-423 (2004).

Counting consistent phylogenetic trees is #P-complete. Abstract.
Bordewich, M., Semple, C., and Talbot, J., Advances in Applied Mathematics, 33:416-430 (2004).

Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs. Abstract.
Bordewich, M., Combinatorics, Probability and Computing, 13(1):1-16, (2004).

The complexity of counting and randomised approximation.
Bordewich, M., D.Phil. Thesis, Oxford University December 2003.

Post-doc:		School of Computer Science, University of Leeds, U.K.
Post-doc:		Biomathematics Research Centre at the
		Department of Mathematics and Statistics, University of Canterbury, New Zealand.
MMath, D.Phil:		Department of Mathematics, University of Oxford, U.K.

	Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width. Abstract. Bordewich, M. and Kang, R. In Press, 2011.
	On the approximation complexity hierarchy. Abstract. Bordewich, M.. In K. Jansen and R. Solis-Oba, editors, Proceedings of WAOA 2010, 8th Workshop on Approximation and Online Algorithms, LNCS. Springer-Verlag, 2010.
	Accuracy Guarantees for Phylogeny Reconstruction Algorithms Based on Balanced Minimum Evolution. Abstract. Bordewich, M. and Mihaescu, R., In V. Moulton and M. Singh, editors, Proceedings of WABI 2010, 10th International Workshop on Algorithms in Bioinformatics, volume 6293 of LNBI, pages 250-261. Springer-Verlag, 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. Abstract. White, T. A., Bordewich, M. and Searle, J. B., Systematic Biology, 59(3):262-276 (2010).
	Consistency of Topological Moves Based on the Balanced Minimum Evolution Principle of Phylogenetic Inference. Abstract. Bordewich, M., Gascuel, O., Huber, K. T. and Moulton, V., Transactions on Computational Biology and Bioinformatics, 6(1):110-117 (2009).
	Optimizing phylogenetic diversity across two trees. Abstract. Bordewich, M., Semple, C. and Spillner, A., Applied Mathematics Letters. 22(5):638-641 (2009).
	Selecting Taxa to Save or Sequence: Desirable Criteria and a Greedy Solution. Abstract. Bordewich, M., Rodrigo, A. G. and Semple, C., Systematic Biology, 57(6):825-834 (2008).
	A 3-approximation algorithm for the subtree distance between phylogenies. Abstract. Bordewich, M., McCartin, C. and Semple, C., Journal of Discrete Algorithms, 6(3):458-471 (2008).
	Nature Reserve Selection Problem: A Tight Approximation Algorithm. Abstract. Bordewich, M., Semple, C., Transactions on Computational Biology and Bioinformatics, 5(2) (2008).
	Path coupling using stopping times and counting independent sets and colourings in hypergraphs. Abstract. Bordewich, M., Dyer, M. and Karpinski, M., Random Structures and Algorithms 32(3):375-399 (2008).
	Optimizing phylogenetic diversity across two trees. Abstract. Bordewich, M., Semple, C. and Spillner, A., Isaac Newton Institute Preprint Series. NI07068-PLG (2007).
	A Reduction Algorithm for Computing the Hybridization Number of Two Trees. Abstract. Bordewich, M., Linz, S., St. John, K. and Semple, C., Evolutionary bioinformatics, 3:86-98 (2007).
	Computing the hybridization number of two phylogenetic trees is fixed-parameter tractable Abstract. Bordewich, M., Semple, C., Transactions on Computational Biology and Bioinformatics,, 4(3):458-466 (2007).
	Path coupling without contraction. Abstract. Bordewich, M. and Dyer, M., Journal of Discrete Algorithms, 5:280-292 (2007).
	Computing the minimum number of hybridisation events for a consistent evolutionary history. Abstract. Bordewich, M., Semple, C., Discrete Applied Mathematics, 155(8):914-928 (2007).
	Stopping times, metrics and approximate counting. Abstract. Bordewich, M., Dyer, M. and Karpinski, M., In proceedings of the 33rd International Colloquium on Automata, Languages and Programming (ICALP 2006), LNCS 4051:108-119, Springer-Verlag.
	Identifying X-trees with few characters. Abstract. Bordewich, M., Semple, C., and Steel, M. The Electronic Journal of Combinatorics, 13 (2006).
	Extending the limits of supertree methods. Abstract. Bordewich, M., Evans, G. and Semple, C., Annals of Combinatorics, 10:31-51 (2006).
	Path coupling using stopping times. Abstract. Bordewich, M., Dyer, M. and Karpinski, M., In proceedings of Fundamentals of Computation Theory (FCT 2005), LNCS 3623:19-31, Springer-Verlag.
	Identifying phylogenetic trees. Abstract. Bordewich, M., Semple, C., and Huber, K., Discrete Mathematics, 300(1-3):30-43 (2005).
	Approximate counting and quantum computation. Abstract. Bordewich, M., Freedman, M., Lovász, L. and Welsh, D., Combinatorics, Probability and Computing, 14(5-6):737-754 (2005).
	On the computational complexity of the rooted subtree prune and regraft distance. Abstract. Bordewich, M., Semple, C., Annals of Combinatorics, 8(4):409-423 (2004).
	Counting consistent phylogenetic trees is #P-complete. Abstract. Bordewich, M., Semple, C., and Talbot, J., Advances in Applied Mathematics, 33:416-430 (2004).
	Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs. Abstract. Bordewich, M., Combinatorics, Probability and Computing, 13(1):1-16, (2004).
	The complexity of counting and randomised approximation. Bordewich, M., D.Phil. Thesis, Oxford University December 2003.