Abstract We derandomize Valiant’s (J ACM 62, Article 13, 2015) subquadratic-time algorithm for finding outlier correlations in binary data. This demonstrates that it is possible to perform a deterministic subquadratic-time similarity join of high dimensionality. 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 by Reingold et al. (Ann Math 155(1):157–187, 2002). We say that a function $$f:\{-1,1\}^d\rightarrow \{-1,1\}^D$$ f : { - 1 , 1 } d → { - 1 , 1 } D is a correlation amplifier with threshold $$0\le \tau \le 1$$ 0 ≤ τ ≤ 1 , error $$\gamma \ge 1$$ γ ≥ 1 , and strength p an even positive integer if for all pairs of vectors $$x,y\in \{-1,1\}^d$$ x , y ∈ { - 1 , 1 } d it holds that (i) $$|\langle x,y\rangle |<\tau d$$ | ⟨ x , y ⟩ | < τ d implies $$|\langle f(x),f(y)\rangle |\le (\tau \gamma )^pD$$ | ⟨ f ( x ) , f ( y ) ⟩ | ≤ ( τ γ ) p D ; and (ii) $$|\langle x,y\rangle |\ge \tau d$$ | ⟨ x , y ⟩ | ≥ τ d implies $$\left (\frac{\langle x,y\rangle }{\gamma d}\right )^pD \le \langle f(x),f(y)\rangle \le \left (\frac{\gamma \langle x,y\rangle }{d}\right )^pD$$ ⟨ x , y ⟩ γ d p D ≤ ⟨ f ( x ) , f ( y ) ⟩ ≤ γ ⟨ x , y ⟩ d p D .

We propose a novel application of coded computing to the problem of the nearest neighbor estimation using MatDot Codes (Fahim et al., Allerton'17) that are known to be optimal for matrix multiplication in terms of recovery threshold under storage constraints. In approximate nearest neighbor algorithms, it is common to construct efficient in-memory indexes to improve query response time. One such strategy is Multiple Random Projection Trees (MRPT), which reduces the set of candidate points over which Euclidean distance calculations are performed. However, this may result in a high memory footprint and possibly paging penalties for large or high-dimensional data. Here we propose two techniques to parallelize MRPT that exploit data and model parallelism respectively by dividing both the data storage and the computation efforts among different nodes in a distributed computing cluster. This is especially critical when a single compute node cannot hold the complete dataset in memory. We also propose a novel coded computation strategy based on MatDot codes for the model-parallel architecture that, in a straggler-prone environment, achieves the storage-optimal recovery threshold, i.e., the number of nodes that are required to serve a query. We experimentally demonstrate that, in the absence of straggling, our distributed approaches require less query time than execution on a single processing node, providing near-linear speedups with respect to the number of worker nodes. Our experiments on real systems with simulated straggling, we also show that in a straggler-prone environment, our strategy achieves a faster query execution than the uncoded strategy.

We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d , and for some constants 0<τ < ρ < 1, we are asked to find all the outlier pairs of vectors whose inner product is at least ρ in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most τ in absolute value. Improving on an algorithm of Valiant [FOCS 2012; J. ACM 2015], we present a randomized algorithm that for Boolean inputs ({ −1,1}-valued data normalized to unit Euclidean length) runs in time Õ(( n max,{ 1−γ + M (Δ γ ,γ), M (1−γ ,2 Δ γ)} + qdn 2γ ), where 0<γ < 1 is a constant tradeoff parameter and M (μ, ν) is the exponent to multiply an ⌊ n μ ⌋ × ⌊ n ν ⌋ matrix with an ⌊ n ν ⌋ × ⌊ n μ ⌋ matrix and Δ =1/(1−log τ ρ). As corollaries we obtain randomized algorithms that run in time Õ( ( n 2/ω 3−log τ ρ + qdn 2/(1−log τ ρ)3=log ττ ρ ) and in time õ( ( n 4 / 2+α (1−log τ ρ) + qdn 2/α (1−log τ ρ)2+α (1−log τ ρ) >), where 2≤ ω <2.38 is the exponent for square matrix multiplication and 0.3<α ≤ 1 is the exponent for rectangular matrix multiplication. The notation Õ(ṡ) hides polylogarithmic factors in n and d whose degree may depend on ρ and τ. We present further corollaries for the light bulb problem and for learning sparse Boolean functions.

This paper presents a technique for symmetry reduction that adaptively assigns a prefix of variables in a system of constraints so that the generated prefix-assignments are pairwise nonisomorphic under the action of the symmetry group of the system. The technique is based on McKay's canonical extension framework (McKay, 1998). Among key features of the technique are (i) adaptability—the prefix sequence can be user-prescribed and truncated for compatibility with the group of symmetries; (ii) parallelizability—prefix-assignments can be processed in parallel independently of each other; (iii) versatility—the method is applicable whenever the group of symmetries can be concisely represented as the automorphism group of a vertex-colored graph; and (iv) implementability—the method can be implemented relying on a canonical labeling map for vertex-colored graphs as the only nontrivial subroutine. To demonstrate the practical applicability of our technique, we have prepared an experimental open-source implementation of the technique and carry out a set of experiments that demonstrate ability to reduce symmetry on hard instances. Furthermore, we demonstrate that the implementation effectively parallelizes to compute clusters with multiple nodes via a message-passing interface.

We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d, and we are asked to find all the outlier pairs of vectors whose inner product is at least ρ in absolute value, subject to the promise that all but at most q pairs of vectors have inner product at most τ in absolute value for some constants 0 < τ < ρ < 1. Improving on an algorithm of G. Valiant [FOCS 2012; J. ACM 2015], we present a randomized algorithm that for Boolean inputs ({–1, 1}-valued data normalized to unit Euclidean length) runs in time where 0 < γ < 1 is a constant tradeoff parameter and M(μ, v) is the exponent to multiply an ⌊nμ⌋ × ⌊nv⌋ matrix with an ⌊nv⌋ × ⌊nμ⌋ matrix and Δ = 1/(1 – logτ ρ). As corollaries we obtain randomized algorithms that run in time and in time where 2 ≤ ω < 2.38 is the exponent for square matrix multiplication and 0.3 < α ≤ 1 is the exponent for rectangular matrix multiplication. We present further corollaries for the light bulb problem and for learning sparse Boolean functions. (The notation Õ(·) hides polylogarithmic factors in n and d whose degree may depend on ρ and τ.)

We consider the problem of maximizing the lifetime of a given multicast connection in a wireless network of energy-constrained (e.g., battery-operated) nodes, by choosing ideal transmission power levels for the nodes relaying the connection. We distinguish between two basic operating modes: In a static power assignment, the power levels of the nodes are set at the beginning and remain unchanged until the nodes are depleted of energy. In a dynamic power schedule, the powers can be adjusted during operation. We show that while lifetime-maximizing static power assignments can be found in polynomial time, for dynamic schedules the problem becomes NP-hard. We introduce two approximation heuristics for the dynamic case, and experimentally verify that the lifetime of a dynamically adjusted multicast connection can be made several times longer than what can be achieved by the best possible static assignment.