Schedule for Alan Frieze's Visit


Thursday, Oct. 11:
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