Phase Transition Phenomena in Combinatorial Problems


(supported under the

EPSRC/London Mathematical Society

MathfIT Initiative)

25th-27th January 1999

Department of Computer Science

University of Liverpool


Monday 25th January 1999

10.00-13.00 Arrival and registration (Moat House, Liverpool)

13.00-14.00 Lunch
14.00-14.10 Opening Remarks (Alan Gibbons)

14.10-15.00 Phase-Transitions: Efficient Algorithms and Combinatorial Properties (Paul E. Dunne and Michele Zito)

Invited Talks

15.00-16.30 The Threshold Problem in Satisfiability of Random Formulae and in Several Models of Random and Semi-random Graphs (Paul Spirakis)

16.30-17.00 Coffee

17.00-18.00 Phase-Transitions in A.I. Research (Ian Gent)

Contributed Talks

18.00-18.30 Critical Behaviour in the Satisfiability of random k-horn formulae (Gabriel Istrate)

18.30-19.00 Sharp Thresholds for `non-trivial' Satisfiability of k-horn formulae (Paul E. Dunne)

19.00 Dinner.

Tuesday 26th January 1999

Invited Talks

09.00-10.00 Phase Transition Behaviour in Constraint Satisfaction Problems (Barbara Smith)

10.00-11.00 Randomly Sampling Unlabelled Structures (Leslie Goldberg)

11.00-11.30 Coffee

11.30-12.15 Sharp Thresholds of Graph Properties, and the k-SAT Problem (Ehud Friedgut)

Contributed Talk

12.15-13.00 Random regular graphs with edge faults (Andreas Goerdt)

13.00-14.00 Lunch

Invited Talks

14.00-15.00 Percolation on transitive graphs: an invitation. (Yuval Peres)

15.00-16.00 The Impact of the Statistical Mechanical Theory of Phase Transitions on Other Branches of Mathematics. (H.N.V. Temperley)

16.00-16.30 Coffee

16.30-17.30 Broadcasting on trees and the Ising model. (Yuval Peres)

Contributed Talks

17.30-18.00 A Phase Transition in Random Coin Tossing (David Levin)

18.00-18.30 Typical-case complexity results from a new type of phase transition (Remi Monasson)

18.30-19.00 k-SAT, spectral gap and cut-off in Markov chains. (Philip Knight)

19.00 Dinner

Wednesday 27th January 1999

Invited Talk

09.00-10.00 Counting Complexity and Phase Transitions (Martin Dyer)

Contributed Talks

10.00-10.30 Compound Poisson Approximations of subgraph counts in random graphs (Dudley Stark)

10.30-11.00 Model clusters and failed cluters in Random k-SAT (Josh Singer)

11.00-11.30 Coffee

Invited Talk

11.30-12.30 Zero-one laws in finite model theory (Iain Stewart)

13.00-14.00 Lunch

End of Programme