Random Sorting Networks


Alexander Holroyd

Theory Group, Microsoft Research


Thursday, February 17, 2011

Talk at 4:30 p.m. in Room 2-190

Tea from 4:00 - 4:30 p.m. in Room 2-290


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 for pictures.


Home Web page:  Alexandru I. Suciu Comments to: 
Posted: February 10, 2011    URL: