Consider collections @math and @math of red and blue sets, respectively. Bichromatic Closest Pair is the problem of finding a pair from @math that has similarity higher than a given threshold according to some similarity measure. Our focus here is the classic Jaccard similarity @math for @math . We consider the approximate version of the problem where we are given thresholds @math and wish to return a pair from @math that has Jaccard similarity higher than @math if there exists a pair in @math with Jaccard similarity at least @math . The classic locality sensitive hashing (LSH) algorithm of Indyk and Motwani (STOC '98), instantiated with the MinHash LSH function of , solves this problem in @math time if @math . In particular, for @math , the approximation ratio @math increases polynomially in @math . In this paper we give a corresponding hardness result. Assuming the Orthogonal Vectors Conjecture (OVC), we show that there cannot be a general solution that solves the Bichromatic Closest Pair problem in @math time for @math . Specifically, assuming OVC, we prove that for any @math there exists an @math such that Bichromatic Closest Pair with Jaccard similarity requires time @math for any choice of thresholds @math , that satisfy @math .
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 coefficient ρ (Hamming distance dċ 1−ρf2), how quickly can one find the two correlated vectorsq We present an algorithm which, for any constant e>0, and constant ρ>0, runs in expected time O(n5mωf4mωpe pnd) Applications and extensions of this basic algorithm yield significantly improved algorithms for several other problems. Approximate Closest Pair. For any sufficiently small constant e>0, given n d-dimensional vectors, there exists an algorithm that returns a pair of vectors whose Euclidean (or Hamming) distance differs from that of the closest pair by a factor of at most 1pe, and runs in time O(n2mΘ(se)). The best previous algorithms (including Locality Sensitive Hashing) have runtime O(n2mO(e)). Learning Sparse Parities with Noise. Given samples from an instance of the learning parities with noise problem where each example has length n, the true parity set has size at most k « n, and the noise rate is η, there exists an algorithm that identifies the set of k indices in time nωpef3 k poly(1f1m2η) 0.4), improves upon the results of [2011] that give a runtime of n(1p(2 η)2 p o(1))kf2 poly(1f1m2η). Learning k-Juntas with Noise. Given uniformly random length n Boolean vectors, together with a label, which is some function of just k « n of the bits, perturbed by noise rate η, return the set of relevant indices. Leveraging the reduction of [2009], our result for learning k-parities implies an algorithm for this problem with runtime nωpef3 k poly(1f1m2η) Learning k-Juntas without Noise. Given uniformly random length n Boolean vectors, together with a label, which is some function of k « n of the bits, return the set of relevant indices. Using a modification of the algorithm of [2004], and employing our algorithm for learning sparse parities with noise via the reduction of [2009], we obtain an algorithm for this problem with runtime nωp ef4 k poly(n)