Princeton Discrete Math Seminar


Random coverings of the n-dimensional cube


Jeong Han Kim
AT&T Labs - Research


Fine Hall 214
Princeton University


3:00 p.m.
Thursday, April 10, 1997

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

Document last modified on April 7, 19997