Alexander Holroyd

Abstract:   Sorting a list of items is one of the most familiar algorithmic problems. If one must do it by swapping neighboring pairs, the worst initial condition is when the n items are in reverse order, in which case n choose 2 swaps are needed. A sorting network is any sequence of n choose 2 swaps that achieves this. We address the question: what does a typical (i.e. uniformly random) n-item sorting network look like? Exact simulations and heuristic arguments have led to a wealth of astonishing conjectures about the n -> infinity limit. For instance, the half-time permutation matrix is believed to be circularly symmetric, while the trajectories of items appear to converge to random sine curves; the best known bounds on the permutation matrices and trajectories are much weaker (but still non-trivial), and arise from a connection with Young tableaux. The conjectures fit together into a remarkable geometric picture. I'll also report on some recent progress on local sub-networks and random sub-networks, both of which shed some new light on this picture. Based on joint works with Omer Angel, Vadim Gorin, Dan Romik and Balint Virag. See http://research.microsoft.com/~holroyd/sort for pictures.