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 | Reply

  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 | Reply

RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Blog at

%d bloggers like this: