The polymath blog

March 2, 2013

Polymath proposal (Tim Gowers): Randomized Parallel Sorting Algorithm

Filed under: polymath proposals — Gil Kalai @ 4:41 pm


From Holroyd’s sorting networks picture gallery

A celebrated theorem of Ajtai, Komlos and Szemeredi describes a sorting network for  $n$ numbers of depth $O(log N)$. rounds where in each runs $n/2$. Tim Gowers proposes to find collectively a randomized sorting with the same properties.


  1. Having read this I believed it was rather enlightening.

    I appreciate you spending some time and effort to put this information together.

    I once again find myself personally spending a lot of time both
    reading and posting comments. But so what, it was still worthwhile!

    Comment by Hotel Konradowka — August 7, 2013 @ 10:38 am

  2. For latest news you have to go to see the web and on web I
    found this web page as a best web page for hottest updates.

    Comment by Lawerence — August 13, 2013 @ 11:15 am

RSS feed for comments on this post.

Blog at

%d bloggers like this: