We show how to compute any symmetric Boolean function on n variables over any field (as well as the integers) with a probabilistic polynomial of degree O(a#x221A;n log(1 a#x03B5;))) and error at most a#x03B5;. The degree dependence on n and a#x03B5; is optimal, matching a lower bound of Razborov (1987) and Smolensky (1987) for the MAJORITY function. The proof is constructive: a low-degree polynomial can be efficiently sampled from the distribution. This polynomial construction is combined with other algebraic ideas to give the first sub quadratic time algorithm for computing a (worst-case) batch of Hamming distances in super logarithmic dimensions, exactly. To illustrate, let c(n): N -> N. Suppose we are given a database D of n vectors in 0, 1 (c(n) log n) and a collection of n query vectors Q in the same dimension. For all u in Q, we wish to compute a v in D with minimum Hamming distance from u. We solve this problem in n(2-1 O(c(n) log2 c(n))) randomized time. Hence, the problem is in "truly sub quadratic" time for O(log n) dimensions, and in sub quadratic time for d = o((log2 n) (log log n)2). We apply the algorithm to computing pairs with maximum inner product, closest pair in l1 for vectors with bounded integer entries, and pairs with maximum Jaccard coefficients.
We propose a new decoding algorithm for random binary linear codes. The so-called information set decoding algorithm of Prange (1962) achieves worst-case complexity (2^ 0.121n ). In the late 80s, Stern proposed a sort-and-match version for Prange’s algorithm, on which all variants of the currently best known decoding algorithms are build. The fastest algorithm of Becker, Joux, May and Meurer (2012) achieves running time (2^ 0.102n ) in the full distance decoding setting and (2^ 0.0494n ) with half (bounded) distance decoding. Given a set of @math @math -dimensional Boolean vectors with the promise that the vectors are chosen uniformly at random with the exception of two vectors that have Pearson -- correlation @math (Hamming distance @math ), how quickly can one find the two correlated vectors? We present an algorithm which, for any constants @math and @math finds the correlated pair with high probability, and runs in time @math given @math vectors in @math , our algorithm returns a pair of vectors whose Euclidean distance differs from that of the closest pair by a factor of at most @math and runs in time @math . The best previous algorithms (including LSH) have runtime @math Learning Sparse Parity with Noise: Given samples from an instance of the learning parity with noise problem where each example has length @math , the true parity set has size at most @math . Learning @math -Juntas without Noise: Our results for learning sparse parities with noise imply an algorithm for learning juntas without noise with runtime $n^ + 4 k poly(n) which improves on the runtime n !+1 ! poly(n) n0:7kpoly(n) of [13].