Partially recursive acceptance/rejection

03/29/2011 - 12:15pm
03/29/2011 - 1:10pm
Mark Huber (Claremont McKenna College)

Many combinatorial structures can be viewed as colorings of a graph. These structures tend to be self-reducible: once you fix the color of a particular node, the remaining problem is a version of the original on a smaller graph. For instance, independent sets of a graph can be viewed as a coloring where nodes are given color 0 or 1, and no two nodes colored 1 are adjacent to one another. The hard core gas model assigns a probability to each independent set proportional to a parameter lambda raised to the number of 1's in the graph. In this talk I will introduce a new protocol for designing algorithms to generate random variates drawn from this type of distribution. Called "partially recursive acceptance/rejection", or PRAR, this protocol can draw samples from self-reducible problems in polynomial time over a restricted set of parameters.

Millikan 208 (Pomona College)