CSAIL Event Calendar

Finding Correlations, Learning Juntas, and the Closest Pair Problem

Consider the following basic problem: given a set of n Boolean vectors with the promise that they are chosen uniformly at random, with the exception of a single pair of vectors that is slightly correlated, how quickly can one find the correlated pair? Can one do
better than the quadratic-time brute-force algorithm? Yes. Approaches such as the Locality Sensitive Hashing (LSH) can find the
correlated pair in time n^(2-O(c)), where c is the correlation of the planted pair, and the constant in the O(c) term has been improved in a series of works. We present a subquadratic time algorithm for this problem, having runtime O(n^1.6) for any constant c>0.

This result is leveraged to yield new algorithmic results for several
other problems, including learning parity with noise, learning juntas (given a function over n variables, in which only k<

See other events that are part of Theory Colloquium 2012/2013

See other events happening in February 2013