Archive for category Invited Talks
I’m speaking about some of the work that I have done on randomly generating, and counting the number of, linear extensions of a poset.
Abstract: Suppose I try to shuffle a deck of n cards by randomly transposing adjacent cards. It turns out you need to do this O(n^3 ln(n)) times to really mix up the deck. Now suppose I add some extra rules that look like: “The King of Hearts must be above the Queen of Spades” or “The Queen of Spades must be above the 9 of Diamonds” and so on. I will shuffle the same way, but if an adjacent transposition would cause me to violate one of my rules, I do not execute the transposition. The surprising fact is that it still takes O(n^3 ln(n)) steps to mix up the deck! Now these shuffles with rules is more formally known as linear extensions of a partial order. In this talk I will show where the O(n^3 ln(n)) is coming from, and show how to exactly draw uniformly from the set of linear extensions. I will also discuss recent work on this problem and why embedding this problem in a continuous context can lead to better algorithms for counting linear extensions.
See here for more details.
The talk that I gave at UMSL can now be downloaded here. This talk describes two different protocols for perfect simulation. The first, Partially Recursive Acceptance Rejection, gives an easy way to generate perfect samples from loosely coupled Markov random fields (such as the Ising model) in linear time without building a Markov chain at all for the problem.
The second part discusses Sequential Acceptance Rejection, a method that has proved useful for problems like approximating the permanent in dense problem instances.
Today I am giving the Algebra/Number Theory/Combinatorics Seminar at the Claremont Colleges. This talk, “What is a #P complete problem” is a prequel in a sense to an earlier talk I gave in the Seminar last year. In the earlier talk, I discussed new methods for approximating the permanent of a matrix. In this talk, I will argue that finding the permanent is a hard problem. One way to characterize hardness of a numerical problem is the notion of number P problems, or #P for short. I will define #P problems and give Ben-Dor and Halevi’s 1993 proof that finding the permanent of a matrix is a #P hard problem, so if we could solve it quickly, any problem in #P could also be solved quickly.
I’m excited to be giving the Math and CS Colloquium at UMSL this week. My talk is written and now I’m just trying to get all my reservations together in one spot. Since this is our Fall Break at CMC, I will be staying the weekend in St. Louis, and am looking forward to getting to know the city a little bit.
I will be giving the Statistics Seminar at UCLA on October 18th. The talk is titled: “Perfect simulation of repulsive point processes”.
Abstract Entities in competition for resources, such as towns in a country or trees in a forest, often are further apart from each other than would be predicted if their spatial distribution was independently uniform. Repulsive point processes are used to model such data, but rarely are these distributions given in closed form. Instead, they can be given as either an algorithmic model, or as a unnormalized density with respect to a spatial Poisson point process. In this talk I will show how to generate random samples exactly from an algorithmic setup called the Matérn Type III model, and from an unnormalized density called the Strauss model. Also, I will discuss effective ways to turn these samples into estimates using these models.
The talk that I gave at Greek Stochastics γ has now been posted to the list of talks on my website here. The talk, entitled “The Paired Product Estimator for normalizing constants of Gibbs distribution” details a method for approximation of partition functions that is markedly faster than previously known methods.
Tomorrow (Wednesday, 4th May) at 6:30 PM Pacific time, I will be hosting a session with my fellow editor Gizem Karaali on the Journal of Humanistic Mathematics for the weekly series run by Math 2.0. Click here to get all the info, including how to download the software to view the event, or catch up on past events.