Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions

We solve an open problem concerning the mixing time of symmetric random walk on the ndimensional cube truncated by a hyperplane, showing that it is polynomial in n. As a consequence, we obtain a fully-polynomial randomized approximation scheme for counting the feasible solutions of a 0-1 knapsack problem. The results extend to the case of any fixed number of hyperplanes. The key ingredient in our analysis is a combinatorial construction we call a "balanced almost uniform permutation, " which seems to be of independent interest