Small-depth counting networks and related topics
Michael Klugerman · DSpace@MIT (Massachusetts Institute of Technology) · 1994
In [5], Aspnes, Herlihy, and Shavit generalized the notion of a sorting network by introducing a class of so called "counting" networks and establishing an O#lg upper bound on the depth complexity of such networks. Their work was motivated by a number of practical applications arising in the domain of asynchronous shared memory machines. In this thesis, we continue the analysis of counting networks and produce a number of new upper bounds on their depths. Our results are predicated on the rich combinatorial structure which counting networks possess. In particular, we present a simple explicit construction of an O(lg n lg lg n)-depth counting network, a randomized construction of an O(lg n)-depth network (which works with extremely high probability), and we present an existential proof of a deterministic O(lg n)-depth network. The latter result matches the trivial (iv n)-depth lower bound to within a constant factor. Our main result is a uniform polynomial-time construction of an O(lg n)-depth counting network which depends heavily on the existential result, but makes use of extractor functions introduced in [25]. Using the extractor, we construct regular high degree bipartite graphs with extremely strong expansion properties. We believe this result is of independent interest.