Expanders, sorting in rounds and superconcentrators of limited depth

摘要

Expanding graphs and superconcentrators are relevant to theoretical computer science in several ways. Here we use finite geometries to construct explicitly highly expanding graphs with essentially the smallest possible number of edges.

Our graphs enable us to improve significantly previous results on a parallel sorting problem, by describing an explicit algorithm to sort n elements in k time units using &Ogr;(nαk) processors, where, e.g., α2 = 7/4.

Using our graphs we can also construct efficient n-superconcentrators of limited depth. For example, we construct an n superconcentrator of depth 3 with &Ogr;(n4/3) edges; better than the previous known results.