Given a sequence of random binary vectors how hard is it to find a linear dependence? Usually the specific distribution of interest can be thought of as having a free parameter n for the dimension of the ambient vector space. This allows the following formalization of our question: is there a threshold function f(n) so that having a linear dependence transitions from very unlikely to very likely as the time reaches f(n)? For many individual distributions this is already an interesting question.

Now, if we were given a known or conjectured threshold we naturally want to know why it should be true. Is there a guiding principle? In fact there are some broad techniques that form the first attack on these problems. In this area we will find there is a nice overlap between methods that are "tractable probabilistically" and methods that are "tractable algorithmically".