What Do Robots Have To Do With sqrt(log n)? -- The n+1 Stack Problem (Mario Szegedy)

Abstract: We have n+1 stacks, each is able to hold at most d items. All stacks are filled to their capacity, except the (n+1)th stack, which is empty. In a single move we can pop the topmost element of a stack and push it onto another stack, which is not filled to its capacity. We give bounds on the number of moves required to permute the nd items in the stacks, for the worst case permutation. Neither the upper nor the lower bounds are trivial.

Joint with Jingjin Yu.