Author name cluster
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.
STOC Conference 2005 Conference Paper
The Thorp shuffle is defined as follows. Cut the deck into two equal piles. Drop the first card from the left pile or the right pile according to the outcome of a fair coin flip; then drop from the other pile. Continue this way until both piles are empty. We show that the mixing time for the Thorp shuffle with 2 d cards is polynomial in d.
FOCS Conference 1999 Conference Paper
We solve an open problem concerning the mixing time of a symmetric random walk on an n-dimensional cube truncated by a hyperplane, showing that it is polynomial in n. As a consequence, we obtain a full-polynomial randomized approximation scheme for counting the feasible solutions of a 0-1 knapsack problem. The key ingredient in our analysis is a combinatorial construction we call a "balanced almost uniform permutation", which seems to be of independent interest.