Next Tuesday at 12:15 I’ll be giving the talk in the Algebra, Number Theory, and Combinatorics Seminar in Claremont. The subject is my shiny new protocol for Perfect Simulation: Partially Recursive Acceptance/Rejection in Millikan 208 at Pomona College. Here’s the abstract:
Abstract. 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.