# Princeton Discrete Math Seminar

## Title:

Random coverings of the n-dimensional cube

## Speaker:

- Jeong Han Kim
- AT&T Labs - Research

## Place:

- Fine Hall 214
- Princeton University

## Time:

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

Abstract:
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