Schedule for Alan Frieze's Visit
Thursday, Oct. 11:
- 09:00-10:30 : meeting with
Christian Scheideler
- 10:30-12:00 : talk in Shaffer Hall, Room 100
- 12:00-01:00 : lunch in the Baltimore Museum of Art (close to NEB)
- meeting times afterwards are still available
To arrange a meeting, please contact
Christian Scheideler
Topic of the talk: Approximate Counting and Sampling
Counting and sampling techniques are important for the solution of a wide
variety of problems ranging from graph problems to geometrical problems,
simulation problems and the evaluation of complex mathematical operations. We
will review progress on problems in the area of approximating the size of and
sampling from large combinatorially defined sets. In particular, we will focus
on methods using rapidly mixing Markov chains. Markov chains are techniques that
allow one to study the behavior of random processes. Typical questions discussed
are ( i ) How many perfect matchings does a given bipartite graph contain
(approximating the permanent) ; ( ii ) How many different proper k - colorings
are there of a given graph? ( iii ) What is the volume of a convex body in R^n,
defined by an oracle? ; ( iv ) What does a typical state look like in the Ising
Model of Statistical Physics?
scheideler@cs.jhu.edu
Last modified: Oct 8 2001