The capacity of majority rule
✍
Shao C. Fang; Santosh S. Venkatesh
📂
Article
📅
1998
🏛
John Wiley and Sons
🌐
English
⚖ 274 KB
Let ނ s y1, 1 denote the vertices of the n-dimensional cube. Let U m be a random m-element subset of ނ n and suppose w g ނ 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 Ž . nr log n is a threshold funct