STORY%MIT-MC@sri-unix.UUCP (03/16/84)
From: Kenneth Byrd Story <STORY @ MIT-MC>
[Forward from the MIT bboard by Laws@SRI-AI.]
DATE: Tuesday, March 20, 1984
TIME: 3:45pm Refreshments
4:00pm Lecture
PLACE: NE43-512a
TITLE: "Sorting Networks"
SPEAKER: Professor Michael Paterson, University of Warwick
Last year, Ajtai, Komlos and Szemeredi published details of a depth O(log n)
comparator network for sorting, thus answering a longstanding open problem.
Their construction is difficult to analyse and the bounds they proved result in
networks of astronomical size. A considerable simplification is presented
which readily yields constructions of more moderate size.
HOST: Professor Tom Leighton