Home Fellowship Teaching Raspberry Pi projects Little Man Computer Eng. and CS

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:
PGP public key: MBordewichPGP

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.
PDF Rapid mixing of subset Glauber dynamics on graphs of bounded tree-width. Abstract.
Bordewich, M. and Kang, R. In Press, 2011.
PDF 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.
PDF 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.
PDF 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).
PDF 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).
PDF Optimizing phylogenetic diversity across two trees. Abstract.
Bordewich, M., Semple, C. and Spillner, A., Applied Mathematics Letters. 22(5):638-641 (2009).
PDF 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).
PDF 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).
PDF Nature Reserve Selection Problem: A Tight Approximation Algorithm. Abstract.
Bordewich, M., Semple, C., Transactions on Computational Biology and Bioinformatics, 5(2) (2008).
PDF 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).
PDF Optimizing phylogenetic diversity across two trees. Abstract.
Bordewich, M., Semple, C. and Spillner, A., Isaac Newton Institute Preprint Series. NI07068-PLG (2007).
PDF 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).
PDF 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).
no PDF Path coupling without contraction. Abstract.
Bordewich, M. and Dyer, M., Journal of Discrete Algorithms, 5:280-292 (2007).
PDF 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).
PDF 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.
PDF Identifying X-trees with few characters. Abstract.
Bordewich, M., Semple, C., and Steel, M. The Electronic Journal of Combinatorics, 13 (2006).
PDF Extending the limits of supertree methods. Abstract.
Bordewich, M., Evans, G. and Semple, C., Annals of Combinatorics, 10:31-51 (2006).
PDF 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.
PDF Identifying phylogenetic trees. Abstract.
Bordewich, M., Semple, C., and Huber, K., Discrete Mathematics, 300(1-3):30-43 (2005).
PDF 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).
PDF 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).
PDF Counting consistent phylogenetic trees is #P-complete. Abstract.
Bordewich, M., Semple, C., and Talbot, J., Advances in Applied Mathematics, 33:416-430 (2004).
PDF Approximating the Number of Acyclic Orientations for a Class of Sparse Graphs. Abstract.
Bordewich, M., Combinatorics, Probability and Computing, 13(1):1-16, (2004).
PDF The complexity of counting and randomised approximation.
Bordewich, M., D.Phil. Thesis, Oxford University December 2003.