Covering cubes by random half cubes, with applications to binary neural networks (Q1271555)

The problem of covering the unit sphere \(S_n\) by \(k\) random vectors lie on the same hemisphere \(S_n\) was considered in the late 1950 and early 1960. Some researchers solved this problem by determining the value of \(k\), with the probability measures on \(S_n\) and consequently it was clear that at least \((2-\varepsilon)n\) random vectors are necessary and \((2+ \varepsilon)n\) vectors are sufficient for this purpose. Subsequently, Furedi proved that the number of binary vectors (vectors from \(Q_n\)) needed to cover \(S_n\) is almost equal to the number of random vectors (not necessarily binary vectors) that are required to cover \(S_n\). The relationships they have established are \[ P_{bs}(n, k)= P_{ss}(n, k)+ O(1/\sqrt n). \] The authors have invoked the question ``How many vectors must be chosen uniformly and independently at random from the hyper-cube \(Q_n\), so that every vector in the same hyper-cube \(Q\), has negative inner product with at least one of the random vectors?'' Subsequently, the authors analyzed it in the theoretical stand point of neural network.