Consider the following basic problem: Given $n$ Boolean vectors chosen uniformly
at random, with the exception of a planted pair of $c$-correlated vectors, how
quickly can one find the correlated pair? Can one do better than the
quadratic-time brute-force algorithm? Yes. We present a new algorithm for this
problem with runtime ${poly(1/c) n^{1.6}}$.

We leverage the ideas of this algorithm to yield improved algorithms for
several other problems, including learning parity with noise, learning juntas
(given a function over n variables in which only $k<<n$ are actually relevant, how
quickly can one find the set of k relevant variables?), and the ${\epsilon}$-approximate
closest pair problem (given $n$ points, find a pair whose euclidean distance is at
most a factor of $1+\epsilon$ larger than that of the closest pair).