The capacity of majority rule

Let 𝔹ⁿ={−1, 1}ⁿ denote the vertices of the n-dimensional cube. Let U(m) be a random m-element subset of 𝔹ⁿ and suppose w ∈𝔹ⁿ 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