CS294-2 Markov Chain Monte Carlo: Foundations Applications Fall 2002 (2007)
Lecturer Alistair, Sinclair Scribes, Gabor Pete, Sam Riesenfeld
utions to the "0-1 knapsack problem" with n objects with weights a i and knapsack capacity b. Theorem 16.1 For any {a i=1 and b, # mix = O(n 4.5+# ). We will prove a weaker polynomial bound...
A note on percolation on Z^d: isoperimetric profile via exponential cluster repulsion (2007)
We show that for all p>p_c(\Z^d) percolation parameters, the probability that the cluster of the origin is finite but has at least t vertices at distance one from the infinite cluster is...
Anchored expansion, percolation and speed (2003)
Chen, Dayue, Peres, Yuval, Pete, Gabor
Benjamini, Lyons and Schramm [Random Walks and Discrete Potential Theory (1999) 56-84] considered properties of an infinite graph G, and the simple random walk on it, that are preserved by random...