We derandomize G. Valiant's [J. ACM 62 (2015) Art. 13] subquadratic-time algorithm for finding outlier correlations in binary data. Our derandomized algorithm gives deterministic subquadratic scaling essentially for the same parameter range as Valiant's randomized algorithm, but the precise constants we save over quadratic scaling are more modest. Our main technical tool for derandomization is an explicit family of correlation amplifiers built via a family of zigzag-product expanders in Reingold, Vadhan, and Wigderson [Ann. of Math. 155 (2002) 157--187]. We say that a function @math is a correlation amplifier with threshold @math , error @math , and strength @math an even positive integer if for all pairs of vectors @math it holds that (i) @math implies @math ; and (ii) @math implies @math .
In small dimensions, Alman and Williams @cite_28 present a randomized algorithm that finds Hamming-near neighbours in a batch-query setting analogous to prob:main in subquadratic time in @math when the dimension is constrained to @math . Recently, Chan and Williams @cite_9 show how to derandomize related algorithm designs; also, Alman, Chan and Williams @cite_10 derandomize the probabilistic polynomials for symmetric Boolean functions used in @cite_28 , achieving deterministic subquadratic batch queries in small dimensions.
@cite_28 @cite_9 @cite_10
1430582609 2263246245 2507428467
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 show how to solve all-pairs shortest paths on n nodes in deterministic n3 2Ω([EQUATION]) time, and how to count the pairs of orthogonal vectors among n 0-1 vectors in d = clogn dimensions in deterministic n2−1 O(logc) time. These running times essentially match the best known randomized algorithms of (Williams, STOC'14) and (Abboud, Williams, and Yu, SODA 2015) respectively, and the ability to count was open even for randomized algorithms. By reductions, these two results yield faster deterministic algorithms for many other problems. Our techniques can also be used to deterministically count k-SAT assignments on n variable formulas in 2n--n O(k) time, roughly matching the best known running times for detecting satisfiability and resolving an open problem of Santhanam (2013). A key to our constructions is an efficient way to deterministically simulate certain probabilistic polynomials critical to the algorithms of prior work, carefully applying small-biased sets and modulus-amplifying polynomials. We design new polynomials for representing threshold functions in three different regimes: probabilistic polynomials of low degree, which need far less randomness than previous constructions, polynomial threshold functions (PTFs) with "nice" threshold behavior and degree almost as low as the probabilistic polynomials, and a new notion of probabilistic PTFs where we combine the above techniques to achieve even lower degree with similar "nice" threshold behavior. Utilizing these polynomial constructions, we design faster algorithms for a variety of problems: @math Offline Hamming Nearest (and Furthest) Neighbors: Given @math red and @math blue points in @math -dimensional Hamming space for @math , we can find an (exact) nearest (or furthest) blue neighbor for every red point in randomized time @math or deterministic time @math . These also lead to faster MAX-SAT algorithms for sparse CNFs. @math Offline Approximate Nearest (and Furthest) Neighbors: Given @math red and @math blue points in @math -dimensional @math or Euclidean space, we can find a @math -approximate nearest (or furthest) blue neighbor for each red point in randomized time near @math . @math SAT Algorithms and Lower Bounds for Circuits With Linear Threshold Functions: We give a satisfiability algorithm for @math circuits with a subquadratic number of linear threshold gates on the bottom layer, and a subexponential number of gates on the other layers, that runs in deterministic @math time. This also implies new circuit lower bounds for threshold circuits. We also give a randomized @math -time SAT algorithm for subexponential-size @math circuits, where the top @math gate and middle @math gates have @math fan-in.