The University of Michigan Combinatorics Seminar
We solve an open problem concerning the mixing time of symmetric random walk on the n-dimensional 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. We also generalize to any fixed number of knapsack constraints (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. This is joint work with Alistair Sinclair.