A Method of Constructing Selection Networks with $O(\log n)$ Depth
Shuji Jimbo, Akira Maruoka · SIAM Journal on Computing · 1996
A classifier with n inputs is a comparator network that classifies a set 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 those in the other. Based on the utilization of expanders, Pippenger constructed classifiers with n inputs whose size is asymptotic to $2n\log _2 n$. In the same spirit, we obtain a relatively simple method of constructing classifiers of depth $O(\log n)$. Consequently, for an arbitrary constant $C > {3 / {\log _2 3 = 1.8927}} \ldots $, we construct classifiers of depth $O(\log n)$ and of size at most $Cn\log _2 n + O(n)$.