Randomized Algorithms (RAND2): Edinburgh Site

Overview

RAND2 ("Randomised Algorithms") is a Working Group funded by the EU Esprit initiative, with sites in Bonn, Edinburgh, Leeds, Lund, Oxford, Paris, and the Weizmann Institute, Rehovot. The active RAND2 members associated with the Edinburgh site are Mark Jerrum (publications) and Leslie Goldberg (publications).

Site reports

Recent workshop

The RAND2 Working Group held a workshop under the auspices of the International Centre for Mathematical Sciences (ICMS) at Edinburgh from Friday 27th to Sunday 29th March, 1998. The workshop took place at the ICMS's headquarters at 14 India Street, Edinburgh.

``Missions''

Visit by Mark Jerrum to the Mathematical Institute, Oxford University, and the Computer Science Department, University of Warwick, March 1997.
(1) research collaboration with Leslie Goldberg and Dominic Welsh;
(2) seminar (repeated at Oxford and Warwick): "Random graphs, coexisting phases, and mixing rates in the Markov chain Monte Carlo method".
British Combinatorial Conference, Queen Mary College, London, July 1997.
Mark Jerrum (participant).
Random Structures and Algorithms Workshop, Poznan, Poland, August 1997.
Lelsie Goldberg (speaker, "Random waiting schemes: protocols for resolving contention");
Mark Jerrum (invited speaker, "Efficient sampling").
Combinatorial Approximation Algorithms Workshop, Schloß Dagstuhl, August 1997.
Mark Jerrum (speaker, "Approximate counting: a short introduction").
RAND2 Meeting, Leeds, September 1997.
Leslie Goldberg (participant);
Mark Jerrum (speaker, "Experiments in exact sampling").
Random Graphs and Combinatorial StructuresMeeting, Oberwolfach, September/October 1997.
Mark Jerrum (speaker, "The Swendsen-Wang process does not always mix rapidly").
RAND2 Meeting, Edinburgh, March 1998.
Leslie Goldberg (speaker, "Contention resolution in multiple-access channels");
Mark Jerrum (local organiser).
14th British Colloquium for Theoretical Computer Science (BCTCS14), St Andrews, March/April 1998.
Leslie Goldberg (invited speaker: ``Contention resolution in multiple-access channels'').

One week visit by Mark Jerrum to the Department of Computer Science, University of Warwick, for research collaboration, April 1998. Main topic: mixing rate of the ``Burnside process''.

Research visit by Leslie Goldberg to DIMACS (Center for Discrete Mathematics and Theoretical Computer Science, Rutgers Univ., NJ) to collaborate with Martin Farach and Sampath Kannan (2 weeks), May 1998. Research discussed: contention resolution, stochastic methods for constructing evolutionary trees, the shortest common superstring problem, stochastic problems concerning communication over noisy channels.

Reading One-Day Combinatorics Colloquium, Reading, May 1998.
Leslie Goldberg (invited speaker: ``Uniform sampling modulo symmetries'').

First meeting of the Erdös Institute, Budapest, July 1998.
Mark Jerrum (participant).

WRASS (Warwick Randomised Algorithms and Stochastic Simulation Tutorial and Workshop), Warwick University, July 1998.
Mark Jerrum (invited speaker, ``Torpid Mixing and Non-Approximability'');
Leslie Goldberg (organiser, tutorial: ``Markov Chain Stability and Contention Resolution'').

Summer school on Probabilistic Methods for Algorithmic Discrete Mathematics, Montpellier, August 1998.
Mark Jerrum (series of invited lectures on ``Rapidly mixing Markov Chains'').

One-week research visit to the Department of Computer Science, University of Warwick by Mark Jerrum and Sampath Kannan, August 1998. Main topic: contention resolution in Ethernet channels.

2nd International Workshop ``Random '98'', Barcelona, October 1998.
Leslie Goldberg (speaker: ``The `Burnside process' converges slowly'').
39th Symposium on Foundations of Computer Science (FOCS39), Palo Alto, CA, USA, November 1998.
Mary Cryan (speaker: ``Evolutionary trees can be learned in polynomial time in the two-state general Markov model'').
Visit by Mark Jerrum to the Computer Science Department, University of Warwick, for research collaboration, December 1998. Main topic: stability of backoff protocols.
EPSRC/LMS Workshop on Phase Transition Phenomena in Combinatorial Problems, Liverpool, January 1999.
Leslie Goldberg (invited speaker: ``Randomly sampling unlabelled structures'').
One-week visit by Leslie Goldberg to the School of Computer Studies, University of Leeds for research collaboration, May 1999. Main topic: extensions of path coupling.
One-week visit by Leslie Goldberg to the School of Computer Science, University of Edinburgh for research collaboration, May 1999. Main topics: stability of backoff protocols and counting unlabelled trees.
RAND2 Workshop, Gif-sur-Yvette, Université de Paris-Sud, May 1999.
Mark Jerrum (speaker, "Independent sets in bounded-degree graphs").
France-Berkeley Workshop Phase Transitions and Complexity, Orsay, Université de Paris-Sud, May 1999.
Mark Jerrum (participant).
ALCOM Workshop, Barcelona, June 1999.
Leslie Goldberg (participant).
Liverpool Algorithms Day, Liverpool, June 1999.
Leslie Goldberg (participant).
Schloß Dagstuhl seminar on Parallel and Distributed Algorithms, July 1999.
Leslie Goldberg (speaker, "Stability of backoff protocols").
Two-week visit by Leslie Goldberg to the Department of Computer and Information Science, University of Pennsylvania for research collaboration, August 1999. Main topic: stability of backoff protocols.
RAND2 Workshop, Oxford University, September 1999.
Leslie Ann Goldberg (speaker: Learning evolutionary trees);
Mark Jerrum (speaker: Counting unlabelled subtrees of a tree is #P-complete).

Web page maintained by Mark Jerrum, mrj@dcs.ed.ac.uk