SODA Conference 2008 Conference Paper
Fast approximation of the permanent for very dense problems
- Mark Huber
- Jenny Law
Author name cluster
Mark Huber
Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.
5 papers
1 author row
Possible papers
5FOCS Conference 2000 Conference Paper
The Randomness Recycler: A New Technique for Perfect Sampling
- James Allen Fill
- Mark Huber
For many probability distributions of interest, it is quite difficult to obtain samples efficiently. Often, Markov chains are employed to obtain approximately random samples from these distributions. The primary drawback to traditional Markov chain methods is that the mixing time of the chain is usually unknown, which makes it impossible to determine how close the output samples are to having the target distribution. The authors present a novel protocol, the randomness recycler (RR), that overcomes this difficulty. Unlike classical Markov chain approaches, an RR-based algorithm creates samples drawn exactly from the desired distribution. Other perfect sampling methods such as coupling from the past, use existing Markov chains, but RR does not use the traditional Markov chain at all. While by no means universally useful, RR does apply to a wide variety of problems. In restricted instances of certain problems, it gives the first expected linear time algorithms for generating samples. The authors apply RR to self-organizing lists, the Ising model, random independent sets, random colorings, and the random cluster model.
SODA Conference 1999 Conference Paper
Efficient Exact Sampling from the Ising Model Using Swendsen-Wang
- Mark Huber