The University of Michigan Combinatorics Seminar


Abstract 

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 fullypolynomial randomized approximation scheme for counting the feasible solutions of a 01 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. 