# Archive for October, 2010

### Report on the AMS Fall Western Meeting

Posted by markhuber in AMS, Invited Talks on October 15, 2010

The AMS meeting was an exciting two days. My talk (which can be downloaded here) went over well, and there was a lot of exciting stuff going on. This includes several sessions organized by folks from Microsoft Research. Allan Sly has brought the upper bound on the computational threshold for the hard core gas model down to meet the lower bound (see here.) My third published paper was on generating random variates from this model, so I was excited to see this result.

### AMS Fall Western Meeting

Posted by markhuber in AMS, Invited Talks on October 8, 2010

Tomorrow I’ll be giving a talk at the Fall Western AMS meeting, at UCLA, in Boelter Hall 2444. The talk is titled “Near-linear time perfect simulation of corrugated surfaces”.

Given a bipartite graph with n nodes, a corrugated surface can be viewed as a vector in [0,1]^{n} such that all nodes in one partition are local maxima, and all the nodes in the other partition are local minima. In order to draw samples from this random landscape, Caracciolo, Rinaldi, and Sportiello (2008) constructed a Markov chain whose stationary distributionwas uniform over the set of corrugated surfaces. They conjectured from experiments that the mixing time of the chain was *O(n* ln *n)* for the special case of a square lattice. Here a new Markov chain is presented that provably mixes in *O(n* ln *n)* time for all bipartite graphs. Like the Caraccilo, et al. chain, this new chain can also be used with coupling from thepast to obtain samples drawn exactly from the desired distribution. Furthermore, this approach can then be combinedwith randomized cooling schedule methods in order to obtain a 1 + ε approximation (with probability at least 1 – δ) of the corrugated surface volume in time *O(n*^{2}(ln *n)*ε^{-2} ln (1/δ)).

### Starting something

So I’m sitting here about to give a talk tomorrow, and I’m thinking two things:

1) I should really promote my talks/papers/research more.

2) That stuff really shouldn’t go on my regular blog.

Hence yet another blog was born! This blog is going to be all about what’s going on with my research. I’ll use this space to relay things that I think are important or interesting in Monte Carlo methods. This includes the usual: talks, papers, upcoming conferences I’m attending, interesting things that happened in class, or anything else that comes in under the research rubric. Unlike my personal blog, I plan to post here at least once a week, every Friday. So let’s get started!