A METHOD OF CONSTRUCTING SELECTION NETWORKS WITH O(LOG N) DEPTH

A classifier with n inputs is a comparator network that classifies a s et of n values into two classes with the same number of values in such a way that each value in one class is at least as large as all of tho se in the other. Based on the utilization of expanders, Pippenger cons tructed classifiers with n inputs whose size is asymptotic to 2n log(2 ) n. In the same spirit, we obtain a relatively simple method of const ructing classifiers of depth O (log n). Consequently, for an arbitrary constant C > 3/log(2) 3 = 1.8927..., we construct classifiers of dept h O (log n) and of size at most Cn log(2) n + O (n).