Programme

Phase Transition Phenomena in Combinatorial Problems

(Workshop)

(supported under the

EPSRC/London Mathematical Society

MathfIT Initiative)

25th-27th January 1999

Department of Computer Science

University of Liverpool

Programme

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