Name
Abstract | ||
|---|---|---|
Let B-n = {-1,1}(n) denote the vertices of the n-dimensional cube. Let U(m) be a random m-element subset of B-n and suppose w is an element of B-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/pi 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. (C) 1998 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1998 | 3.3.CO;2-#" target="_self" class="small-link-text"10.1002/(SICI)1098-2418(199801)12:13.3.CO;2-# | Random Struct. Algorithms |
Keywords | Field | DocType |
majority rule,perceptron,capacity | Binary integer programming,Discrete mathematics,Combinatorics,Majority rule,Perceptron,Mathematics,Threshold function | Journal |
Volume | Issue | ISSN |
12 | 1 | 1042-9832 |
Citations | PageRank | References |
3 | 0.48 | 2 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shao C. Fang | 1 | 13 | 4.86 |
| Santosh S. Venkatesh | 2 | 381 | 71.80 |