Finding Correlations in Subquadratic Time, with Applications to Learning Parities and Juntas

摘要

Given a set of $n$ $d$-dimensional Boolean vectors with the promise that the vectors are chosen uniformly at random with the exception of two vectors that have Pearson -- correlation $rho$ (Hamming distance $dcdot frac{1-rho}{2}$), how quickly can one find the two correlated vectors? We present an algorithm which, for any constants $eps, rho>0$ and $d >>frac{log n}{rho^2}, $ finds the correlated pair with high probability, and runs in time $O(n^{frac{3 omega}{4}+eps}) 0, $ given $n$ vectors in $R^d$, our algorithm returns a pair of vectors whose Euclidean distance differs from that of the closest pair by a factor of at most $1+eps, $ and runs in time $O(n^{2-Theta(sqrt{eps})})$. The best previous algorithms (including LSH) have runtime $O(n^{2-O(eps)}). $ Learning Sparse Parity with Noise: Given samples from an instance of the learning parity with noise problem where each example has length $n$, the true parity set has size at most $k n^{k(1-frac{2}{2^k})} poly(frac{1}{1-2eta})$. Learning $k$-Juntas without Noise: Our results for learning sparse parities with noise imply an algorithm for learning juntas without noise with runtime $n^{frac{omega+ eps}{4} k} poly(n) which improves on the runtime n !+1 ! poly(n) n0:7kpoly(n) of Mossel et al. [13].