Giving talk in Claremont ANTC seminar next week

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.

Advertisements
  1. Leave a comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: