Mike's mini-workshop on Algorithms is a workshop to honor Mike Paterson's numerous contributions to theoretical computer science, the University of Warwick, and DIMAP. The workshop is organized jointly by the Centre for Discrete Mathematics and its Applications (DIMAP) and the Algorithms and Computational Complexity Research Group at the Department of Computer Science, University of Warwick, December 14, 2009. The workshop will take place on the campus of the University of Warwick, at the Centre for Discrete Mathematics and its Applications (DIMAP), in the building of the the Department of Computer Science (number 13 on the campus map). We plan to provide lunch buffet for the participants, but to properly estimate the number of lunches we will need participants to register.

---

---

Abstracts:

• Mark Jerrum (Queen Mary London): A Complexity Dichotomy for Hypergraph Partition Functions
  
  

  We consider the complexity of counting homomorphisms from an r-uniform hypergraph G to a symmetric r-ary relation H. We give a dichotomy theorem for r>2, showing for which H this problem is in FP and for which H it is #P-complete. This generalises a theorem of Dyer and Greenhill (2000) for the case r=2, which corresponds to counting graph homomorphisms. Our dichotomy theorem extends to the case in which the relation H is weighted, and the goal is to compute the partition function, which is the sum of weights of the homomorphisms. This problem is motivated by statistical physics, where it arises as computing the partition function for particle models in which certain combinations of r sites interact symmetrically. In the weighted case, our dichotomy theorem generalises a result of Bulatov and Grohe (2005) for graphs, where r=2. When r=2, the polynomial time cases of the dichotomy correspond simply to rank-1 weights. Surprisingly, for all r>2 the polynomial-time cases of the dichotomy have rather more structure. It turns out that the weights must be superimposed on a combinatorial structure defined by solutions of an equation over an Abelian group. Our result also gives a dichotomy for a closely related constraint satisfaction problem.

  Joint work with Martin E. Dyer (University of Leeds) and Leslie Ann Goldberg (University of Liverpool).

  ---

• Martin E. Dyer (University of Leeds): The Dynamics of Games on Graphs
  
  

  We consider simple games played on the edges of a graph, by agents situated at the vertices. We study the evolution of cooperation amongst the agents. This gives rise to processes resembling the particle systems of statistical physics, though the dynamics involved are rather different.

  ---

• Leslie Ann Goldberg (University of Liverpool): Stable Marriages and Independent Sets in Bipartite Graphs
  
  

  The classical ``stable marriage problem'' is described as follows. Given n men and n women, where each person has ranked all members of of the opposite sex with a unique number between 1 and n in order of preference, a ``stable'' matching is a bijection from the men to the women such that there are no two people of opposite sex who would both rather have each other than their current partners. Gale and Shapley showed in 1962 that a stable matching always exists and they gave an efficient algorithm for constructing one.

  Some recent attention has focussed on the problem of selecting a stable matching uniformly at random. Bhatnagar, Greenberg and Randall considered a certain natural Markov chain, and showed that it is slowly mixing, even when stable marriage instances are drawn from restricted geometric models.

  It turns out that, even in these restricted models, the problem of selecting a stable matching uniformly at random is closely connected to the (still open) problem of sampling an independent set uniformly at random in a bipartite graph, which in turn is equivalent to many well-known sampling problems and is complete in a logically-defined complexity class.

  Joint work with Prasad Chebolu and Russell Martin (University of Liverpool).

  ---

• Mike Paterson (University of Warwick): Open!
  
  

  I'd like help with some problems that have captured my attention over the last few decades. I will present a handful of open questions drawn from several areas.

---

Organizers

• Artur Czumaj
• Harald Räcke