We consider the problem of randomly generating 0-1 contingency tables.
This is a well-studied problem in statistics, as well as the theory of random graphs, since it is equivalent to generating a random bipartite graph with a prescribed degree sequence. Previously, the only algorithm known for all degree sequences was by reduction to approximating the permanent of a 0-1 matrix. We give a direct combinatorial algorithm which relies on simulated annealing and also improve the efficiency as a byproduct. An interesting aspect of the annealing algorithm is that the high temperature distribution for the annealing is defined algorithmically.

This is joint work with Ivona Bezakova and Eric Vigoda.