This talk will consider the following combinatorial problem which comes from neural networks.
The (n-dimensional) half-space generated by an n-dimensional real vector x is the set of all w in R^n having negative inner product with x. Let Q_n be the n-dimensional cube {1, -1}^n. How many random vectors in Q_n (with every vector in Q_n equally likely to be chosen) are needed so that the half spaces generated by the random vectors will cover Q_n ?
It is easy to see that (1+o(1))n random vectors are sufficient. Are (1-o(1))n random vectors necessary? The answer is ``NO''. It may be shown that 0.9963n are sufficient and 0.005n are necessary.
We will also see how this problem is related to neural networks. (Joint work with J. Roche.)
Next week: Jeff Kahn