The capacity of majority rule

Let n ={−1, 1} n denote the vertices of the n ‐dimensional cube. Let U ( m ) be a random m ‐element subset of n and suppose w ∈ n is a vertex closest to the centroid of U ( m ). Using a large deviation, multivariate local limit theorem due to Richter, we show that n /π log  n is a threshold function for the property that the convex hull of U ( m ) is contained in the positive half‐space determined by w . The decision problem considered here is an instance of binary integer programming, and the algorithm selecting w as the vertex closest to the centroid of U ( m ) has been previously dubbed majority rule in the context of learning binary weights for a perceptron. © 1998 John Wiley & Sons, Inc.  Random Struct. Alg. , 12, 83–109, 1998