Name
Abstract | ||
|---|---|---|
Harmonic update is a randomized on-line algorithm which, given a random $m$-set of vertices $U(m)\subseteq\{-1,1\}^n$ in the $n$-dimensional cube, generates a random vertex $\bw\in\{-1,1\}^n$ as a putative solution to the system of linear inequalities: $\sum_{i=1}^n w_i u_i\geq0$ for each $\bu\in U(m)$. Using tools from large deviation multivariate normal approximation and Poisson approximation, we show that $\sqrt{n}\big/\!\sqrt{\log n}$ is a threshold function for the property that the vertex $\bw$ generated by harmonic update has positive inner product with each vertex in $U(m)$. More explicitly, let $P(n,m)$ denote the probability that $\sum_{i=1}^n w_i u_i\geq 0$ for each $\bu\in U(m)$. Then, as $n\to\infty$, $P(n,m)\to 0$ or $1$ according to whether $m=m_n$ varies with $n$ such that $m\gg\sqrt{n}\big/\!\sqrt{\log n}$ or $m\ll\sqrt{n}\big/\!\sqrt{\log n}$, respectively. The analysis also exposes the fine structure of the threshold function. |
Year | DOI | Venue |
|---|---|---|
1997 | 10.1137/S0895480195283701 | SIAM J. Discrete Math. |
Keywords | Field | DocType |
large deviation multivariate,n w_i u_i,harmonic update,threshold function,fine structure,random vertex,poisson approximation,log n,dimensional cube,normal approximation,neural networks,randomized algorithm,polytopes,large deviations | Binary integer programming,Discrete mathematics,Combinatorics,Vertex (geometry),Combinatorial mathematics,Harmonic,Normal approximation,Polytope,Mathematics,Threshold function | Journal |
Volume | Issue | ISSN |
10 | 3 | 0895-4801 |
Citations | PageRank | References |
1 | 0.36 | 3 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shao C. Fang | 1 | 13 | 4.86 |
| Santosh S. Venkatesh | 2 | 381 | 71.80 |