We develop algorithms for the approximate Orthogonal Vectors (OV) and Diameter problems over the Hamming space. Prior work exhibited an intriguing sharp transition: for approximation factor c=2, the algorithms are simple and run in Õ(nd) time; whereas already for c=2-δ, the best known approach has been to reduce the problems to nearest neighbor search, leading to solutions with runtimes of the form n1+ω(1). Our algorithms solve (2-δ)-approximate OV and Diameter with runtimes of n1+O(δ) and n1+O(√δ), respectively. The improvement also holds for the online (data structure) versions: online OV and Furthest Neighbor Search (FNS). This is the first direct improvement for approximate FNS in the Hamming space since [Goel, Indyk, Varadarajan 2001]. Our approach consists of two key steps. First, we define a "heterogeneous"pseudo-random instance of the problems and prove a structural lemma showing that any such instance is solved by one of three simple algorithms. Second, we develop a specialized regularity lemma that allows one to reduce any arbitrary dataset to such a pseudo-random instance.

We introduce the notion of metric embeddings into a similarity measure over $\mathbb{R}_{+}^{m}$, such as the weighted Jaccard coefficient. We develop average embeddings into such similarity measures for a number of metric spaces, with (appropriately defined) distortion that is smaller than the best possible or known distortion of embedding into $\ell_{1}$ or $\ell_{2}$ spaces (biLipschitz or average). We complement our embeddings with a new algorithm for Approximate Nearest Neighbor Search (ANNS) that leverages such an embedding in a black box fashion. Combining these results, we obtain new efficient algorithms for ANNS under the following two classic metrics, achieving an exponential improvement to longstanding prior work: - Edit distance over length- k strings: $\operatorname{poly}(\log k)$ approximation; - $\ell_{p}$ over $\mathbb{R}^{d}$, for $p\gt2: O(\log p)$ approximation (known to be asymptotically optimal in relevant models of computation).

Transformers have the representational capacity to simulate Massively Parallel Computation (MPC) algorithms, but they suffer from quadratic time complexity, which severely limits their scalability. We introduce an efficient attention mechanism called Approximate Nearest Neighbor Attention (ANNA) with sub-quadratic time complexity. We prove that ANNA-transformers (1) retain the expressive power previously established for standard attention in terms of matching the capabilities of MPC algorithms, and (2) can solve key reasoning tasks such as Match2 and $k$-hop with near-optimal depth. Using the MPC framework, we further prove that constant-depth ANNA-transformers can simulate constant-depth low-rank transformers, thereby providing a unified way to reason about a broad class of efficient attention approximations.

We present a general framework for designing efficient data structures for high-dimensional pattern-matching problems ($\exists \;? i\in[n], f(x_i,y)=1$) through communication models in which $f(x,y)$ admits sublinear communication protocols with exponentially-small error. Specifically, we reduce the data structure problem to the Unambiguous Arthur-Merlin (UAM) communication complexity of $f(x,y)$ under product distributions. We apply our framework to the Partial Match problem (a.k.a, matching with wildcards), whose underlying communication problem is sparse set-disjointness. When the database consists of $n$ points in dimension $d$, and the number of $\star$'s in the query is at most $w = c\log n \;(\ll d)$, the fastest known linear-space data structure (Cole, Gottlieb and Lewenstein, STOC'04) had query time $t \approx 2^w = n^c$, which is nontrivial only when $c<1$. By contrast, our framework produces a data structure with query time $n^{1-1/(c \log^2 c)}$ and space close to linear. To achieve this, we develop a one-sided $ε$-error communication protocol for Set-Disjointness under product distributions with $\tildeΘ(\sqrt{d\log(1/ε)})$ complexity, improving on the classical result of Babai, Frankl and Simon (FOCS'86). Building on this protocol, we show that the Unambiguous AM communication complexity of $w$-Sparse Set-Disjointness with $ε$-error under product distributions is $\tilde{O}(\sqrt{w \log(1/ε)})$, independent of the ambient dimension $d$, which is crucial for the Partial Match result. Our framework sheds further light on the power of data-dependent data structures, which is instrumental for reducing to the (much easier) case of product distributions.

We study the density estimation problem defined as follows: given $k$ distributions $p_1, \ldots, p_k$ over a discrete domain $[n]$, as well as a collection of samples chosen from a "query" distribution $q$ over $[n]$, output $p_i$ that is "close" to $q$. Recently Aamand et al. gave the first and only known result that achieves sublinear bounds in both the sampling complexity and the query time while preserving polynomial data structure space. However, their improvement over linear samples and time is only by subpolynomial factors. Our main result is a lower bound showing that, for a broad class of data structures, their bounds cannot be significantly improved. In particular, if an algorithm uses $O(n/\log^c k)$ samples for some constant $c>0$ and polynomial space, then the query time of the data structure must be at least $k^{1-O(1)/\log \log k}$, i.e., close to linear in the number of distributions $k$. This is a novel statistical-computational trade-off for density estimation, demonstrating that any data structure must use close to a linear number of samples or take close to linear query time. The lower bound holds even in the realizable case where $q=p_i$ for some $i$, and when the distributions are flat (specifically, all distributions are uniform over half of the domain $[n]$). We also give a simple data structure for our lower bound instance with asymptotically matching upper bounds. Experiments show that the data structure is quite efficient in practice.

We study graph spanners for point-set in the high-dimensional Euclidean space. On the one hand, we prove that spanners with stretch $\lt \sqrt{2}$ and subquadratic size are not possible, even if we add Steiner points. On the other hand, if we add extra nodes to the graph (non-metric Steiner points), then we can obtain $(1+\epsilon)$-approximate spanners of subquadratic size. We show how to construct a spanner of size $n^{2-\Omega\left(\epsilon^{3}\right)}$, as well as a directed version of the spanner of size $n^{2-\Omega\left(\epsilon^{2}\right)}$. We use our directed spanner to obtain an algorithm for computing $(1+\epsilon)$-approximation to Earth-Mover Distance (optimal transport) between two sets of size n in time $n^{2-\Omega\left(\epsilon^{2}\right)}$.

We study statistical/computational tradeoffs for the following density estimation problem: given $k$ distributions $v_1, \ldots, v_k$ over a discrete domain of size $n$, and sampling access to a distribution $p$, identify $v_i$ that is "close" to $p$. Our main result is the first data structure that, given a sublinear (in $n$) number of samples from $p$, identifies $v_i$ in time sublinear in $k$. We also give an improved version of the algorithm of Acharya et al. (2018) that reports $v_i$ in time linear in $k$. The experimental evaluation of the latter algorithm shows that it achieves a significant reduction in the number of operations needed to achieve a given accuracy compared to prior work.

Range counting (e.g., counting the number of data points falling into a given query ball) under differential privacy has been studied extensively. However, the current algorithms for this problem are subject to the following dichotomy. One class of algorithms suffers from an additive error that is a fixed polynomial in the number of points. Another class of algorithms allows for polylogarithmic additive error, but the error grows exponentially in the dimension. To achieve the latter, the problem is relaxed to allow a “fuzzy” definition of the range boundary, e.g., a count of the points in a ball of radius $r$ might also include points in a ball of radius $cr$ for some $c>1$. In this paper we present an efficient algorithm that offers a sweet spot between these two classes. The algorithm has an additive error that is an arbitrary small power of the data set size, depending on how fuzzy the range boundary is, as well as a small ($1+o(1)$) multiplicative error. Crucially, the amount of noise added has no dependence on the dimension. Our algorithm introduces a variant of Locality-Sensitive Hashing, utilizing it in a novel manner.

Efficient computation on massive high-dimensional data greatly benefits from efficient embedding techniques into simpler metrics. Perhaps the most celebrated technique is the dimension reduction a-la Johnson and Lindenstrauss [46]. Another important method embeds the data into a tree metric space, first efficiently achieved by Bartal [15]. Both of these algorithmic tools are among the most general theorems with numerous applications.

Longest Increasing Subsequence (LIS) is a fundamental statistic of a sequence, and has been studied for decades. While the LIS of a sequence of length n can be computed exactly in time $O(n\log n)$, the complexity of estimating the (length of the) LIS in sublinear time, especially when LIS $\ll n$, is still open. We show that for any $n\in\mathbb{N}$ and $\lambda=o(1)$, there exists a (randomized) non-adaptive algorithm that, given a sequence of length n with LIS $\geq\lambda n$, approximates the LIS up to a factor of $1/\lambda^{o(1)}$ in $ n^{o(1)}/\lambda$ time. Our algorithm improves upon prior work substantially in terms of both approximation and run-time: (i) we provide the first sub-polynomial approximation for LIS in sub-linear time; and (ii) our run-time complexity essentially matches the trivial sample complexity lower bound of $\Omega(1/\lambda)$, which is required to obtain any non-trivial approximation of the LIS. As part of our solution, we develop two novel ideas which may be of independent interest. First, we define a new Genuine-LIS problem, in which each sequence element may be either genuine or corrupted. In this model, the user receives unrestricted access to the actual sequence, but does not know a priori which elements are genuine. The goal is to estimate the LIS using genuine elements only, with the minimal number of tests for genuineness. The second idea, Precision Tree, enables accurate estimations for composition of general functions from “coarse” (sub-)estimates. Precision Tree essentially generalizes classical precision sampling, which works only for summations. As a central tool, the Precision Tree is pre-processed on a set of samples, which thereafter is repeatedly used by multiple components of the algorithm, improving their amortized complexity.

The indexing algorithms for the high-dimensional nearest neighbor search (NNS) with the best worst-case guarantees are based on the randomized Locality Sensitive Hashing (LSH), and its derivatives. In practice, many heuristic approaches exist to "learn" the best indexing method in order to speed-up NNS, crucially adapting to the structure of the given dataset. Oftentimes, these heuristics outperform the LSH-based algorithms on real datasets, but, almost always, come at the cost of losing the guarantees of either correctness or robust performance on adversarial queries, or apply to datasets with an assumed extra structure/model. In this paper, we design an NNS algorithm for the Hamming space that has worst-case guarantees essentially matching that of theoretical algorithms, while optimizing the hashing to the structure of the dataset (think instance-optimal algorithms) for performance on the minimum-performing query. We evaluate the algorithm’s ability to optimize for a given dataset both theoretically and practically. On the theoretical side, we exhibit a natural setting (dataset model) where our algorithm is much better than the standard theoretical one. On the practical side, we run experiments that show that our algorithm has a 1.8x and 2.1x better recall on the worst-performing queries to the MNIST and ImageNet datasets.

We show improved data structures for the high-dimensional approximate nearest neighbor search problem (ANN) for ℓp distances for “large” values of p and for generalized Hamming distances. The previous best data structures proceeded by embedding a metric of interest into the ℓ∞ space or an ℓ∞-direct sum with simple summands, and then using data structures of Indyk (FOCS 1998, SoCG 2002) for ℓ∞-ANN. In contrast to this, we bypass the embedding step and proceed by extending the technique underlying the ℓ∞ data structures to handle ℓp and generalized Hamming distances directly. The resulting data structures are randomized, in contrast to Indyk's result for ℓ∞-ANN, and replicate input points, in contrast with Locality Sensitive Hashing. This leads to ANN data structures with significantly improved approximations over those implied by embeddings, as well as those obtained using all known approaches based on random space partitions.

This issue of SICOMP contains 14 specially selected papers from the 48th Annual ACM Symposium on Theory of Computing (STOC 2016), held June 18--June 21, 2016, in Cambridge, Massachusetts. The papers here were chosen to represent both the excellence and the broad range of the STOC program. The papers have been revised and extended by the authors and subjected to the standard thorough reviewing process of SICOMP. The program committee members were Alexandr Andoni, Sanjeev Arora, Allison Bishop, Avrim Blum, Keren Censor-Hillel, Timothy Chan, Chandra Chekuri, Jing Chen, Zeev Dvir, Fabrizio Grandoni, Parikshit Gopalan, Kasper Green Larsen, Huijia (Rachel) Lin, Konstantin Makarychev, Yishay Mansour (chair), Jakob Nordström, Debmalya Panigrahi, Prasad Raghavendra, Sofya Raskhodnikova, R Ravi, Mario Szegedy, Êva Tardos, Salil Vadhan, Avi Wigderson, and Ronald de Wolf. We briefly describe here the papers that appear in this special issue. In “Breaking the Logarithmic Barrier for Truthful Combinatorial Auctions with Submodular Bidders,” Shahar Dobzinski provides the first truthful mechanism for welfare maximization in combinatorial auctions with submodular bidders whose approximation ratio is $O(\sqrt{\log m})$. Previously the best ratio was $O(\log m)$. In “A Tight Space Bound for Consensus,” Leqi Zhu proves that every randomized wait-free (or obstruction-free) consensus protocol for $n$ processes must use at least $n-1$ registers. Previously, this bound was known only in the anonymous setting, while for the general case only a $\sqrt{n}$ bound was known. In “Two-Source Dispersers for Polylogarithmic Entropy and Improved Ramsey Graphs,” Gil Cohen constructs a $2^{(\log\log n)^c}$-Ramsey graph for some universal constant $c$, a significant improvement in this direction. In the language of theoretical computer science, this resolves the problem of explicitly constructing dispersers for two $n$-bit sources with entropy ${polylog}(n)$. Previously, such dispersers could only support entropy $\Omega(n)$. In “Algorithmic Bayesian Persuasion,” Shaddin Dughmi and Haifeng Xu examines Bayesian persuasion through a computational lens for the first time. When the payoff distributions are i.i.d. across actions, the authors provide a polynomial-time optimal solution and a “simple” $(1-1/e)$-approximation. For independent but nonidentical distributions, \#P-hardness is proved. For the general case with a black-box sampling oracle, an FPTAS is provided and shown to be the best possible under the black-box model. In “A Deterministic Almost-Tight Distributed Algorithm for Approximating Single-Source Shortest Paths,” Monika Henzinger, Sebastian Krinninger, and Danupon Nanongkai present a deterministic $(1 + o(1))$-approximation algorithm for solving the single-source shortest paths problem on distributed weighted networks in $O(n^{1/2+o(1)} + D^{1+o(1)})$ rounds, where $n$ is the number of nodes and $D$ is the diameter of the network. This improves upon previous results in being deterministic and completing in less time or in obtaining a smaller approximation factor. Moreover, it is almost tight due to a known lower bound. In “Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines,” Nikhil Bansal, Aravind Srinivasan, and Ola Svensson improve, by a small but fixed constant, the long-standing approximation factor of $3/2$ for the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. In “A Duality-Based Unified Approach to Bayesian Mechanism Design,” Yang Cai, Nikhil Devanur, and Seth Matthew Weinberg provide a duality-based unified framework for designing simple and approximately optimal auctions. Using this framework, the authors prove that either a posted-price mechanism or the Vickrey--Clarke--Groves auction with per-bidder entry fees achieves a constant-factor of the optimal revenue achievable by a Bayesian Incentive Compatible mechanism whenever buyers are unit-demand or additive, unifying previous breakthroughs of Chawla et al. and Yao, and improving both approximation ratios. In “A $(1+\varepsilon)$-Approximation for Makespan Scheduling with Precedence Constraints using LP Hierarchies,” Elaine Levey and Thomas Rothvoss consider the problem of scheduling $n$ unit size jobs with a precedence order on $m$ identical machines as to minimize the makespan. They prove that for any fixed $\epsilon$ and $m$, an LP-hierarchy lift of the time-indexed LP with a slightly super poly-logarithmic number of $r = (\log n)^{\Theta(\log \log n)}$ rounds provides a $(1 + \epsilon)$-approximation. The previous best approximation algorithms for this problem guarantee a $(2 - 7/(3m+1))$-approximation in polynomial time for $m \ge 4$ and $4/3$ for $m=3$. In “Bipartite Perfect Matching Is in Quasi-${{NC}}$,” Stephen Fenner, Rohit Gurjar, and Thomas Thierauf show that the bipartite perfect matching problem is in quasi-${{NC}}^2$. That is, it has uniform circuits of quasi-polynomial size $n^{O(\log n)}$, and $O(\log^2 n)$ depth. Previously, only an exponential upper bound was known on the size of such circuits with poly-logarithmic depth. In “Exponential Separation of Communication and External Information,” Anat Ganor, Gillat Kol, and Ran Raz prove the first gap, an exponential gap, between external information complexity and communication complexity of a communication task. Previously such a separation was known only for the internal information vs communication complexity. This result has implication to the question of compressing communication protocols to the amount of information they reveal about the inputs. In “Constant-Round Interactive Proofs for Delegating Computation,” Omer Reingold, Guy Rothblum, and Ron Rothblum design efficient, constant-round interactive proofs. They show that for any statement that can be evaluated in polynomial time and space $S$, there exists a constant-round interactive protocol where the prover has polynomial runtime and the verifier has a runtime of about $n+\poly(S)$. Prior to this work, very little was known about the power of constant-round protocol. This result is a major step for the grand challenge of verifiable delegation of computation. In “Tight Bounds for Single-Pass Streaming Complexity of the Set Cover Problem,” Sepehr Assadi, Sanjeev Khanna, and Yang Li resolve the space complexity of single-pass streaming algorithms for approximating the classic set cover problem. For finding an $\alpha$-approximate set cover (for any $\alpha= o(\sqrt{n})$) using a single-pass streaming algorithm, they show that $\Theta(mn/\alpha)$ space is both sufficient and necessary (up to an $O(\log n)$ factor), where $m$ denotes number of the sets and $n$ denotes size of the universe. They further study the problem of estimating the size of a minimum set cover (as opposed to finding the actual sets) and achieve an additional saving of a factor of $\alpha$ in the space complexity, which is also the best possible. In “A Polynomial Lower Bound for Testing Monotonicity,” Aleksandrs Belovs and Eric Blais show a polynomial lower bound on query complexity for adaptive testers of monotonicity of an $n$-variate Boolean function. Prior to this work, similar lower bounds were known only for the nonadaptive testers, and proving similar bounds for adaptive testers has been a major challenge. In “Algorithmic Stability for Adaptive Data Analysis,” Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman take a solid step forward in the area of adaptive data analysis by establishing a clean, tight connection between the notion of differential privacy (max-KL stability) and design of adaptive queries. This connection improves a number of bounds that were known prior to this paper, and generalizes to handle more “data analysis" settings. We thank the authors, the program committee members, and the reviewers for STOC 2016 for their hard work, and we especially thank the SICOMP reviewers for their work in evaluating submitted papers.

We study the space complexity of solving the bias-regularized SVM problem in the streaming model. In particular, given a data set (x_i,y_i) ∈ ℝ^d× {-1,+1}, the objective function is F_λ(θ,b) = λ/2‖(θ,b)‖₂² + 1/n∑_{i=1}ⁿ max{0,1-y_i(θ^Tx_i+b)} and the goal is to find the parameters that (approximately) minimize this objective. This is a classic supervised learning problem that has drawn lots of attention, including for developing fast algorithms for solving the problem approximately: i.e., for finding (θ,b) such that F_λ(θ,b) ≤ min_{(θ',b')} F_λ(θ',b')+ε. One of the most widely used algorithms for approximately optimizing the SVM objective is Stochastic Gradient Descent (SGD), which requires only O(1/λε) random samples, and which immediately yields a streaming algorithm that uses O(d/λε) space. For related problems, better streaming algorithms are only known for smooth functions, unlike the SVM objective that we focus on in this work. We initiate an investigation of the space complexity for both finding an approximate optimum of this objective, and for the related "point estimation" problem of sketching the data set to evaluate the function value F_λ on any query (θ, b). We show that, for both problems, for dimensions d = 1,2, one can obtain streaming algorithms with space polynomially smaller than 1/λε, which is the complexity of SGD for strongly convex functions like the bias-regularized SVM [Shalev-Shwartz et al., 2007], and which is known to be tight in general, even for d = 1 [Agarwal et al., 2009]. We also prove polynomial lower bounds for both point estimation and optimization. In particular, for point estimation we obtain a tight bound of Θ(1/√{ε}) for d = 1 and a nearly tight lower bound of Ω̃(d/{ε}²) for d = Ω(log(1/ε)). Finally, for optimization, we prove a Ω(1/√{ε}) lower bound for d = Ω(log(1/ε)), and show similar bounds when d is constant.

Abstract. We present an algorithm for approximating the edit distance between two strings of length [Formula: see text] in time [Formula: see text] up to a constant factor for any [Formula: see text]. Our result completes a research direction set forth in the recent breakthrough paper [ CDG[Formula: see text]18 ], which showed the first constant-factor approximation algorithm with a (strongly) subquadratic running time. Recent results [ KS20b , BR20 ] have shown near-linear time algorithms that obtain an additive approximation, near-linear in [Formula: see text] (equivalently, constant-factor approximation when the edit distance value is close to [Formula: see text]). In contrast, our algorithm obtains a constant-factor approximation in near-linear time for any input string. In contrast to prior algorithms, which are mostly recursing over smaller substrings, our algorithm gradually smoothes out the local contribution to the edit distance over progressively larger substrings. To accomplish this, we iteratively construct a distance oracle data structure for the metric of edit distance on all substrings of input strings of length [Formula: see text] for [Formula: see text]. The distance oracle approximates the edit distance over these substrings in a certain average sense, just enough to estimate the overall edit distance.

We present a (1+ε)-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving poly(logn) depth and m poly(logn) work for n-nodes m-edges graphs. Although sequential algorithms with (nearly) optimal running time have been known for several decades, near-optimal parallel algorithms have turned out to be a much tougher challenge. For (1+ε)-approximation, all prior algorithms with poly(logn) depth perform at least Ω(mn c ) work for some constant c>0. Improving this long-standing upper bound obtained by Cohen (STOC’94) has been open for 25 years.

We study the problem of learning a real-valued function of correlated variables. Solving this problem is of interest since many classical learning results apply only in the case of learning functions of random variables that are independent. We show how to recover a high-dimensional, sparse monomial model from Gaussian examples with sample complexity that is poly-logarithmic in the total number of variables and polynomial in the number of relevant variables. Our algorithm is based on a transformation of the variables—taking their logarithm—followed by a sparse linear regression procedure, which is statistically and computationally efficient. While this transformation is commonly used in applied non-linear regression, its statistical guarantees have never been rigorously analyzed. We prove that the sparse regression procedure succeeds even in cases where the original features are highly correlated and fail to satisfy the standard assumptions required for sparse linear regression.

We study the problem of discrete distribution testing in the two-party setting. For example, in the standard closeness testing problem, Alice and Bob each have t samples from, respectively, distributions a and b over [n], and they need to test whether a=b or a,b are epsilon-far (in the l_1 distance). This is in contrast to the well-studied one-party case, where the tester has unrestricted access to samples of both distributions. Despite being a natural constraint in applications, the two-party setting has previously evaded attention. We address two fundamental aspects of the two-party setting: 1) what is the communication complexity, and 2) can it be accomplished securely, without Alice and Bob learning extra information about each other’s input. Besides closeness testing, we also study the independence testing problem, where Alice and Bob have t samples from distributions a and b respectively, which may be correlated; the question is whether a,b are independent or epsilon-far from being independent. Our contribution is three-fold: 1) We show how to gain communication efficiency given more samples, beyond the information-theoretic bound on t. The gain is polynomially better than what one would obtain via adapting one-party algorithms. 2) We prove tightness of our trade-off for the closeness testing, as well as that the independence testing requires tight Omega(sqrt{m}) communication for unbounded number of samples. These lower bounds are of independent interest as, to the best of our knowledge, these are the first 2-party communication lower bounds for testing problems, where the inputs are a set of i.i.d. samples. 3) We define the concept of secure distribution testing, and provide secure versions of the above protocols with an overhead that is only polynomial in the security parameter.

Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data --- data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model. In this paper, we study two fundamental problems, $2$-edge connectivity and $2$-vertex connectivity (biconnectivity). PRAM algorithms which run in $O(\log n)$ time have been known for many years. We give algorithms using roughly log diameter rounds in the MPC model. Our main results are, for an $n$-vertex, $m$-edge graph of diameter $D$ and bi-diameter $D'$, 1) a $O(\log D\log\log_{m/n} n)$ parallel time $2$-edge connectivity algorithm, 2) a $O(\log D\log^2\log_{m/n}n+\log D'\log\log_{m/n}n)$ parallel time biconnectivity algorithm, where the bi-diameter $D'$ is the largest cycle length over all the vertex pairs in the same biconnected component. Our results are fully scalable, meaning that the memory per processor can be $O(n^δ)$ for arbitrary constant $δ>0$, and the total memory used is linear in the problem size. Our $2$-edge connectivity algorithm achieves the same parallel time as the connectivity algorithm of Andoni et al. (FOCS 2018). We also show an $Ω(\log D')$ conditional lower bound for the biconnectivity problem.

We study \emph{sublinear} algorithms that solve linear systems locally. In the classical version of this problem the input is a matrix $S\in \mathbb{R}^{n\times n}$ and a vector $b\in\mathbb{R}^n$ in the range of $S$, and the goal is to output $x\in \mathbb{R}^n$ satisfying $Sx=b$. For the case when the matrix $S$ is symmetric diagonally dominant (SDD), the breakthrough algorithm of Spielman and Teng [STOC 2004] approximately solves this problem in near-linear time (in the input size which is the number of non-zeros in $S$), and subsequent papers have further simplified, improved, and generalized the algorithms for this setting. Here we focus on computing one (or a few) coordinates of $x$, which potentially allows for sublinear algorithms. Formally, given an index $u\in [n]$ together with $S$ and $b$ as above, the goal is to output an approximation $\hat{x}_u$ for $x^*_u$, where $x^*$ is a fixed solution to $Sx=b$. Our results show that there is a qualitative gap between SDD matrices and the more general class of positive semidefinite (PSD) matrices. For SDD matrices, we develop an algorithm that approximates a single coordinate $x_{u}$ in time that is polylogarithmic in $n$, provided that $S$ is sparse and has a small condition number (e.g., Laplacian of an expander graph). The approximation guarantee is additive $| \hat{x}_u-x^*_u | \le ε\| x^* \|_\infty$ for accuracy parameter $ε>0$. We further prove that the condition-number assumption is necessary and tight. In contrast to the SDD matrices, we prove that for certain PSD matrices $S$, the running time must be at least polynomial in $n$. This holds even when one wants to obtain the same additive approximation, and $S$ has bounded sparsity and condition number.

We study bi-Hölder homeomorphisms between the unit spheres of finite-dimensional normed spaces and use them to obtain better data structures for the high-dimensional Approximate Near Neighbor search (ANN) in general normed spaces. Our main structural result is a finite-dimensional quantitative version of the following theorem of Daher (1993) and Kalton (unpublished). Every d-dimensional normed space X admits a small perturbation Y such that there is a bi-Holder homeomorphism with good parameters between the unit spheres of Y and Z, where Z is a space that is close to ℓ_2^d. Furthermore, the bulk of this article is devoted to obtaining an algorithm to compute the above homeomorphism in time polynomial in d. Along the way, we show how to compute efficiently the norm of a given vector in a space obtained by the complex interpolation between two normed spaces. We demonstrate that, despite being much weaker than bi-Lipschitz embeddings, such homeomorphisms can be efficiently utilized for the ANN problem. Specifically, we give two new data structures for ANN over a general d-dimensional normed space, which for the first time achieve approximation d^o(1), thus improving upon the previous general bound O(sqrtd) that is directly implied by John's theorem.

Many modern parallel systems, such as MapReduce, Hadoop and Spark, can be modeled well by the MPC model. The MPC model captures well coarse-grained computation on large data — data is distributed to processors, each of which has a sublinear (in the input data) amount of memory and we alternate between rounds of computation and rounds of communication, where each machine can communicate an amount of data as large as the size of its memory. This model is stronger than the classical PRAM model, and it is an intriguing question to design algorithms whose running time is smaller than in the PRAM model. One fundamental graph problem is connectivity. On an undirected graph with n nodes and m edges, O(log n) round connectivity algorithms have been known for over 35 years. However, no algorithms with better complexity bounds were known. In this work, we give fully scalable, faster algorithms for the connectivity problem, by parameterizing the time complexity as a function of the diameter of the graph. Our main result is a O(log D log log_m/n n) time connectivity algorithm for diameter-d graphs, using Θ(m) total memory. If our algorithm can use more memory, it can terminate in fewer rounds, and there is no lower bound on the memory per processor. We extend our results to related graph problems such as spanning forest, finding a DFS sequence, exact/approximate minimum spanning forest, and bottleneck spanning forest. We also show that achieving similar bounds for reachability in directed graphs would imply faster boolean matrix multiplication algorithms. We introduce several new algorithmic ideas. We describe a general technique called double exponential speed problem size reduction which roughly means that if we can use total memory n to reduce a problem from size n to n/k, for k=(N/n)^Θ(1) in one phase, then we can solve the problem in O(loglog_N/n n) phases. In order to achieve this fast reduction for graph connectivity, we use a multistep algorithm. One key step is a carefully constructed truncated broadcasting scheme where each node broadcasts neighbor sets to its neighbors in a way that limits the size of the resulting neighbor sets. Another key step is random leader contraction, where we choose a smaller set of leaders than many previous works do.

We consider a generalization of the classic linear regression problem to the case when the loss is an Orlicz norm. An Orlicz norm is parameterized by a non-negative convex function G: R_+ - > R_+ with G(0) = 0: the Orlicz norm of a n-dimensional vector x is defined as |x|_G = inf{ alpha > 0 | sum_{i = 1}^n G( |x_i| / alpha ) < = 1 }. We consider the cases where the function G grows subquadratically. Our main result is based on a new oblivious embedding which embeds the column space of a given nxd matrix A with Orlicz norm into a lower dimensional space with L2 norm. Specifically, we show how to efficiently find an mxn embedding matrix S (m < n), such that for every d-dimensional vector x, we have Omega(1/(d log n)) |Ax|_G < = |SAx|_2 < = O(d^2 log n) |Ax|_G. By applying this subspace embedding technique, we show an approximation algorithm for the regression problem min_x |Ax-b|_G, up to a O( d log^2 n ) factor. As a further application of our techniques, we show how to also use them to improve on the algorithm for the Lp low rank matrix approximation problem for 1 < = p < 2.

We establish a generic reduction from _nonlinear spectral gaps_ of metric spaces to data-dependent Locality-Sensitive Hashing, yielding a new approach to the high-dimensional Approximate Near Neighbor Search problem (ANN) under various distance functions. Using this reduction, we obtain the following results:

An outstanding open question (http://sublinear.info, Question #5) asks to characterize metric spaces in which distances can be estimated using efficient sketches. Specifically, we say that a sketching algorithm is efficient if it achieves constant approximation using constant sketch size. A well-known result of Indyk (J. ACM, 2006) implies that a metric that admits a constant-distortion embedding into lp for p∈(0,2] also admits an efficient sketching scheme. But is the converse true, i.e., is embedding into lp the only way to achieve efficient sketching? We address these questions for the important special case of normed spaces, by providing an almost complete characterization of sketching in terms of embeddings. In particular, we prove that a finite-dimensional normed space allows efficient sketches if and only if it embeds (linearly) into l1-ε with constant distortion. We further prove that for norms that are closed under sum-product, efficient sketching is equivalent to embedding into l1 with constant distortion. Examples of such norms include the Earth Mover's Distance (specifically its norm variant, called Kantorovich-Rubinstein norm), and the trace norm (a.k.a. Schatten 1-norm or the nuclear norm). Using known non-embeddability theorems for these norms by Naor and Schechtman (SICOMP, 2007) and by Pisier (Compositio. Math., 1978), we then conclude that these spaces do not admit efficient sketches either, making progress towards answering another open question (http://sublinear.info, Question #7).

This article studies the correspondence retrieval problem: a set of $k$ distinct but unknown points $\mathbf{x}_1, \mathbf{x}_2, \dotsc, \mathbf{x}_k ∈\mathbb{R}^d$ are to be recovered from the unordered collection of projection values $⟨\mathbf{w}_i,\mathbf{x}_1 ⟩, ⟨\mathbf{w}_i,\mathbf{x}_2 ⟩, \dotsc, ⟨\mathbf{w}_i,\mathbf{x}_k ⟩$ onto $n$ known measurement vectors $\mathbf{w}_1, \mathbf{w}_2, \dotsc, \mathbf{w}_n$. Importantly, the correspondence of the $k$ projections ${⟨\mathbf{w}_i,\mathbf{x}_j ⟩}_j=1^k$ across different measurements is unknown. A special case of this problem is the well-studied problem of (real-valued) phase retrieval. In the case of independent standard Gaussian measurement vectors, the main algorithm proposed in this work requires $n = d+1$ measurements to correctly return the $k$ unknown points with high probability. This number of measurements is optimal, and it is smaller than the number of measurements required for a stronger “for all” guarantee even in the phase retrieval setting. The algorithm is based on reductions to the Shortest Vector Problem on certain random lattices, and employs the Lenstra, Lenstra, and Lovász (1982) basis reduction algorithm in a manner similar to the Lagarias & Odlyzko (1985) algorithm for solving random instances of Subset Sum. Another algorithm, essentially due to Yi, Caramanis, & Sanghavi (2016), based on higher-order moments and tensor decompositions is shown to work in a setting where the projection values are corrupted by additive Gaussian noise, but it requires a significantly larger number of measurements.

We present anew, simple algorithm for sketching the k > 2 frequency moment of a dynamic stream, or simply the ℓknorm of a vector in the linear sketching model. The new algorithms are based on exponentially distributed random variables, which possess a certain “max-stability” property, similar in spirit to the “p-stability” property used in [Indyk, JACM'06] for sketching ℓknorms for k ≤ 2. Our resulting sketching algorithm can be seen as a “weak embedding” of an n-dimensional ℓkspace into 1∞space of dimension m = O(n1-2/klog n): it preserves the norm of a vector up to constant approximation, with constant probability. We note that this dimension is optimal for linear embeddings (sketches) with constant approximation, as shown in [Andoni-Nguyen-Polyanskiy-Wu, ICALP'13]. The preliminary version of this result has appeared as a blog post in 2012, and its main idea has since been used in other streaming algorithms.

We show tight upper and lower bounds for time-space trade-offs for the c-approximate Near Neighbor Search problem. For the d-dimensional Euclidean space and n-point datasets, we develop a data structure with space n1+ρu+o(1) + O(dn) and query time nρq +o(1) + dno(1) for every ρu, ρq ≥ 0 with: In particular, for the approximation c = 2 we get: Space n1.77… and query time no(1), significantly improving upon known data structures that support very fast queries [IM98, KOR00]; Space n1.14… and query time n0.14…, matching the optimal data-dependent Locality-Sensitive Hashing (LSH) from [AR15]; Space n1+o(1) and query time n0‘43 ‘, making significant progress in the regime of near-linear space, which is arguably of the most interest for practice [LJW+07]. This is the first data structure that achieves sublinear query time and near-linear space for every approximation factor c > 1, improving upon [Kap15]. The data structure is a culmination of a long line of work on the problem for all space regimes; it builds on Spherical Locality-Sensitive Filtering [BDGL16] and data- dependent hashing [AINR14, AR15]. Our matching lower bounds are of two types: conditional and unconditional. First, we prove tightness of the whole trade-off (0.1) in a restricted model of computation, which captures all known hashing-based approaches. We then show unconditional cell-probe lower bounds for one and two probes that match (0.1) for ρq = 0, improving upon the best known lower bounds from [PTW10]. In particular, this is the first space lower bound (for any static data structure) for two probes which is not polynomially smaller than the one-probe bound. To show the result for two probes, we establish and exploit a connection to locally-decodable codes.

We analyze LSH Forest [BCG05]—a popular heuristic for the nearest neighbor search—and show that a careful yet simple modification of it outperforms “vanilla” LSH algorithms. The end result is the first instance of a simple, practical algorithm that provably leverages data-dependent hashing to improve upon data-oblivious LSH. Here is the entire algorithm for the d-dimensional Hamming space. The LSH Forest, for a given dataset, applies a random permutation to all the d coordinates, and builds a trie on the resulting strings. In our modification, we further augment this trie: for each node, we store a constant number of points close to the mean of the corresponding subset of the dataset, which are compared to any query point reaching that node. The overall data structure is simply several such tries sampled independently. While the new algorithm does not quantitatively improve upon the best data-dependent hashing algorithms from [AR15] (which are known to be optimal), it is significantly simpler, being based on a practical heuristic, and is provably better than the best LSH algorithm for the Hamming space [IM98, HIM12].

We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every n, d = no(1), and every d-dimensional symmetric norm ||·||, there exists a data structure for (loglogn)-approximate nearest neighbor search over ||·|| for n-point datasets achieving no(1) query time and n1+o(1) space. The main technical ingredient of the algorithm is a low-distortion embedding of a symmetric norm into a low-dimensional iterated product of top-k norms.

No abstract available.

We prove a tight lower bound for the exponent rho for data-dependent Locality-Sensitive Hashing schemes, recently used to design efficient solutions for the c-approximate nearest neighbor search. In particular, our lower bound matches the bound of rho<= 1/(2c-1)+o(1) for the l_1 space, obtained via the recent algorithm from [Andoni-Razenshteyn, STOC'15]. In recent years it emerged that data-dependent hashing is strictly superior to the classical Locality-Sensitive Hashing, when the hash function is data-independent. In the latter setting, the best exponent has been already known: for the l_1 space, the tight bound is rho=1/c, with the upper bound from [Indyk-Motwani,STOC'98] and the matching lower bound from [O'Donnell-Wu-Zhou,ITCS'11]. We prove that, even if the hashing is data-dependent, it must hold that rho>=1/(2c-1)-o(1). To prove the result, we need to formalize the exact notion of data-dependent hashing that also captures the complexity of the hash functions (in addition to their collision properties). Without restricting such complexity, we would allow for obviously infeasible solutions such as the Voronoi diagram of a dataset. To preclude such solutions, we require our hash functions to be succinct. This condition is satisfied by all the known algorithmic results.

Transportation cost metrics, also known as the Wasserstein distances W_p, are a natural choice for defining distances between two pointsets, or distributions, and have been applied in numerous fields. From the computational perspective, there has been an intensive research effort for understanding the W_p metrics over R^k, with work on the W_1 metric (a.k.a earth mover distance) being most successful in terms of theoretical guarantees. However, the W_2 metric, also known as the root-mean square (RMS) bipartite matching distance, is often a more suitable choice in many application areas, e.g. in graphics. Yet, the geometry of this metric space is currently poorly understood, and efficient algorithms have been elusive. For example, there are no known non-trivial algorithms for nearest-neighbor search or sketching for this metric. In this paper we take the first step towards explaining the lack of efficient algorithms for the W_2 metric, even over the three-dimensional Euclidean space R^3. We prove that there are no meaningful embeddings of W_2 over R^3 into a wide class of normed spaces, as well as that there are no efficient sketching algorithms for W_2 over R^3 achieving constant approximation. For example, our results imply that: 1) any embedding into L1 must incur a distortion of Omega(sqrt(log(n))) for pointsets of size n equipped with the W_2 metric; and 2) any sketching algorithm of size s must incur Omega(sqrt(log(n))/sqrt(s)) approximation. Our results follow from a more general statement, asserting that W_2 over R^3 contains the 1/2-snowflake of all finite metric spaces with a uniformly bounded distortion. These are the first non-embeddability/non-sketchability results for W_2.

We undertake a systematic study of sketching a quadratic form: given an n x n matrix A, create a succinct sketch sk(A) which can produce (without further access to A) a multiplicative (1+ε)-approximation to xT A x for any desired query x ∈ Rn. While a general matrix does not admit non-trivial sketches, positive semi-definite (PSD) matrices admit sketches of size θ(ε{-2 n), via the Johnson-Lindenstrauss lemma, achieving the "for each" guarantee, namely, for each query x, with a constant probability the sketch succeeds. (For the stronger "for all" guarantee, where the sketch succeeds for all x's simultaneously, again there are no non-trivial sketches.)

In this article, we show how to compute the width of a dynamic set of low-dimensional points in the streaming model. In particular, we assume that the stream contains both insertions of points and deletions of points to a set S , and the goal is to compute the width of the set S , namely the minimal distance between two parallel hyperplanes sandwiching the point set S . Our algorithm (1 + ϵ) approximates the width of the set S using space polylogarithmic in the size of S and the aspect ratio of S . This is the first such algorithm that supports both insertions and deletions of points to the set S : previous algorithms for approximating the width of a point set only supported additions [Agarwal et al. 2004; Chan 2006], or a sliding window [Chan and Sadjad 2006]. This solves an open question from the “2009 Kanpur list” of open problems in data streams, property testing, and related topics [Indyk et al. 2011].

We show the existence of a Locality-Sensitive Hashing (LSH) family for the angular distance that yields an approximate Near Neighbor Search algorithm with the asymptotically optimal running time exponent. Unlike earlier algorithms with this property (e.g., Spherical LSH (Andoni-Indyk-Nguyen-Razenshteyn 2014) (Andoni-Razenshteyn 2015)), our algorithm is also practical, improving upon the well-studied hyperplane LSH (Charikar 2002) in practice. We also introduce a multiprobe version of this algorithm and conduct an experimental evaluation on real and synthetic data sets.We complement the above positive results with a fine-grained lower bound for the quality of any LSH family for angular distance. Our lower bound implies that the above LSH family exhibits a trade-off between evaluation time and quality that is close to optimal for a natural class of LSH functions.

We show an optimal data-dependent hashing scheme for the approximate near neighbor problem. For an n-point dataset in a d-dimensional space our data structure achieves query time O(d ⋅ nρ+o(1)) and space O(n1+ρ+o(1) + d ⋅ n), where ρ=1/(2c2-1) for the Euclidean space and approximation c>1. For the Hamming space, we obtain an exponent of ρ=1/(2c-1). Our result completes the direction set forth in (Andoni, Indyk, Nguyen, Razenshteyn 2014) who gave a proof-of-concept that data-dependent hashing can outperform classic Locality Sensitive Hashing (LSH). In contrast to (Andoni, Indyk, Nguyen, Razenshteyn 2014), the new bound is not only optimal, but in fact improves over the best (optimal) LSH data structures (Indyk, Motwani 1998) (Andoni, Indyk 2006) for all approximation factors c>1.

We study spectral algorithms for the high-dimensional Nearest Neighbor Search problem (NNS). In particular, we consider a semi-random setting where a dataset is chosen arbitrarily from an unknown subspace of low dimension, and then perturbed by full-dimensional Gaussian noise. We design spectral NNS algorithms whose query time depends polynomially on the dimension and logarithmically on the size of the point set. These spectral algorithms use a repeated computation of the top PCA vector/subspace, and are effective even when the random-noise magnitude is much larger than the interpoint distances. Our motivation is that in practice, a number of spectral NNS algorithms outperform the random-projection methods that seem otherwise theoretically optimal on worst-case datasets. In this paper we aim to provide theoretical justification for this disparity. The full version of this extended abstract is available on arXiv.

We study the effectiveness of learning low degree polynomials using neural networks by the gradient descent method. While neural networks have been shown to have great expressive power, and gradient descent has been widely used in practice for learning neural networks, few theoretical guarantees are known for such methods. In particular, it is well known that gradient descent can get stuck at local minima, even for simple classes of target functions. In this paper, we present several positive theoretical results to support the effectiveness of neural networks. We focus on two-layer neural networks (i.e. one hidden layer) where the top layer node is a linear function, similar to \citebarron93. First we show that for a randomly initialized neural network with sufficiently many hidden units, the gradient descent method can learn any low degree polynomial. Secondly, we show that if we use complex-valued weights (the target function can still be real), then under suitable conditions, there are no “robust local minima”: the neural network can always escape a local minimum by performing a random perturbation. This property does not hold for real-valued weights. Thirdly, we discuss whether sparse polynomials can be learned with \emphsmall neural networks, where the size is dependent on the sparsity of the target function.

We present a new data structure for the c-approximate near neighbor problem (ANN) in the Euclidean space. For n points in ℝd, our algorithm achieves Oc(nρ + dlogn) query time and Oc(n1+ρ + dlogn) space, where ρ ≤ 7/(8c2) + O(1/c3) + oc(1). This is the first improvement over the result by Andoni and Indyk (FOCS 2006) and the first data structure that bypasses a locality-sensitive hashing lower bound proved by O'Donnell, Wu and Zhou (ICS 2011). By a standard reduction we obtain a data structure for the Hamming space and ℓ1 norm with ρ ≤ 7/(8c)+ O(1/c3/2)+ oc(1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).

We study the question of learning a sparse multivariate polynomial over the real domain. In particular, for some unknown polynomial f(x) of degree-d and k monomials, we show how to reconstruct f, within error ∊, given only a set of examples xi drawn uniformly from the n-dimensional cube (or an n-dimensional Gaussian distribution), together with evaluations f(i) on them. The result holds even in the “noisy setting”, where we have only values f(i) + g where g is noise (say modeled as a Gaussian random variable). The runtime of our algorithm is polynomial in n, k, 1/∊ and Cd where Cd depends only on d. Note that, in contrast, in the “boolean version” of this problem, where is drawn from the hypercube, the problem is at least as hard as the “noisy parity problem,” where we do not know how to break the nΩ(d) time barrier, even for k = 1, and some believe it may be impossible to do so.

We give algorithms for geometric graph problems in the modern parallel models such as MapReduce. For example, for the Minimum Spanning Tree (MST) problem over a set of points in the two-dimensional space, our algorithm computes a (1 + ε)-approximate MST. Our algorithms work in a constant number of rounds of communication, while using total space and communication proportional to the size of the data (linear space and near linear time algorithms). In contrast, for general graphs, achieving the same result for MST (or even connectivity) remains a challenging open problem [9], despite drawing significant attention in recent years.

We study the following basic pattern matching problem. Consider a “code” sequence c consisting of n bits chosen uniformly at random, and a “signal” sequence x obtained by shifting c (modulo n) and adding noise. The goal is to efficiently recover the shift with high probability. The problem models tasks of interest in several applications, including GPS synchronization and motion estimation. We present an algorithm that solves the problem in time Õ(n(f/(1+f)), where Õ(Nf) is the running time of the best algorithm for finding the closest pair among N “random” sequences of length O(log N). A trivial bound of f = 2 leads to a simple algorithm with a running time of Õ(n2/3). The asymptotic running time can be further improved by plugging in recent more efficient algorithms for the closest pair problem. Our results also yield a sub-linear time algorithm for approximate pattern matching algorithm for a random signal (text), even for the case when the error between the signal and the code (pattern) is asymptotically as large as the code size. This is the first sublinear time algorithm for such error rates.

We study the question of estimating the eigenvalues of a matrix in the streaming model, addressing a question posed in [Mut05]. We show that the eigenvalue “heavy hitters” of a matrix can be computed in a single pass. In particular, we show that the φ-heavy hitters (in the ℓ or ℓ2 norms) can be estimated in space proportional to . Such a dependence on is optimal. We also show how the same techniques may give an estimate of the residual error tail of a rank-k approximation of the matrix (in the Frobenius norm), in space proportional to k2. All our algorithms are linear and hence can support arbitrary updates to the matrix in the stream. In fact, what we show can be seen as a form of a bi-linear dimensionality reduction: if we multiply an input matrix with projection matrices on both sides, the resulting matrix preserves the top eigenvalues and the residual Frobenius norm.

Fingerprinting is a widely-used technique for efficiently verifying that two files are identical. More generally, linear sketching is a form of lossy compression (based on random projections) that also enables the "dissimilarity" of non-identical files to be estimated. Many sketches have been proposed for dissimilarity measures that decompose coordinate-wise such as the Hamming distance between alphanumeric strings, or the Euclidean distance between vectors. However, virtually nothing is known on sketches that would accommodate alignment errors. With such errors, Hamming or Euclidean distances are rendered useless: a small misalignment may result in a file that looks very dissimilar to the original file according such measures. In this paper, we present the first linear sketch that is robust to a small number of alignment errors. Specifically, the sketch can be used to determine whether two files are within a small Hamming distance of being a cyclic shift of each other. Furthermore, the sketch is homomorphic with respect to rotations: it is possible to construct the sketch of a cyclic shift of a file given only the sketch of the original file. The relevant dissimilarity measure, known as the shift distance, arises in the context of embedding edit distance and our result addressed an open problem [Question 13 in Indyk-McGregor-Newman-Onak'11] with a rather surprising outcome. Our sketch projects a length $n$ file into D(n) ⋅ polylog n dimensions where D(n)l n is the number of divisors of n. The striking fact is that this is near-optimal, i.e., the D(n) dependence is inherent to a problem that is ostensibly about lossy compression.

We show how to compute the width of a dynamic set of low-dimensional points in the streaming model. In particular, we assume the stream contains both insertions of points and deletions of points to a set S, and the goal is to compute the width of the set S, namely the minimal distance between two parallel lines sandwiching the pointset S. Our algorithm 1 + ε approximates the width of the set S using space polylogarithmic in the size of S and the aspect ratio of S. This is the first such algorithm that supports both insertions and deletions of points to the set S: previous algorithms for approximating the width of a pointset only supported additions [AHPV04, Cha06], or a sliding window [CS06]. This solves an open question from the “2009 Kanpur list” of Open Problems in Data Streams, Property Testing, and Related Topics [IMNO11].

We show how to compute the edit distance between two strings of length $n$ up to a factor of $2^{\tilde{O}(\sqrt{\log n})}$ in $n^{1+o(1)}$ time. This is the first subpolynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art $n^{1/3+o(1)}$ approximation. Previously, approximation of $2^{\tilde{O}(\sqrt{\log n})}$ was known only for embedding edit distance into $\ell_1$, and it is not known if that embedding can be computed in less than quadratic time.

We initiate the study of the smoothed complexity of sequence alignment, by proposing a semi-random model of edit distance between two input strings, generated as follows: First, an adversary chooses two binary strings of length d and a longest common subsequence A of them. Then, every character is perturbed independently with probability p , except that A is perturbed in exactly the same way inside the two strings. We design two efficient algorithms that compute the edit distance on smoothed instances up to a constant factor approximation. The first algorithm runs in near-linear time, namely d {1+ϵ} for any fixed ϵ > 0. The second one runs in time sublinear in d , assuming the edit distance is not too small. These approximation and runtime guarantees are significantly better than the bounds that were known for worst-case inputs. Our technical contribution is twofold. First, we rely on finding matches between substrings in the two strings, where two substrings are considered a match if their edit distance is relatively small, a prevailing technique in commonly used heuristics, such as PatternHunter of Ma et al. [2002]. Second, we effectively reduce the smoothed edit distance to a simpler variant of (worst-case) edit distance, namely, edit distance on permutations (a.k.a. Ulam's metric). We are thus able to build on algorithms developed for the Ulam metric, whose much better algorithmic guarantees usually do not carry over to general edit distance.

Given a set of n points in ℓ1, how many dimensions are needed to represent all pair wise distances within a specific distortion? This dimension-distortion tradeoff question is well understood for the ℓ2norm, where O((log n)/ϵ2) dimensions suffice to achieve 1+ϵ distortion. In sharp contrast, there is a significant gap between upper and lower bounds for dimension reduction in ℓ1. A recent result shows that distortion 1+ϵ can be achieved with n/ϵ2dimensions. On the other hand, the only lower bounds known are that distortion δ requires nΩ(1/δ2)dimensions and that distortion 1+ϵ requires n1/2-O(ϵ log(1/ϵ))dimensions. In this work, we show the first near linear lower bounds for dimension reduction in ℓ1. In particular, we show that 1+ϵ distortion requires at least n1-O(1/log(1/ϵ))dimensions. Our proofs are combinatorial, but inspired by linear programming. In fact, our techniques lead to a simple combinatorial argument that is equivalent to the LP based proof of Brinkman-Charikar for lower bounds on dimension reduction in ℓ1.

A technique introduced by Indyk and Woodruff (STOC 2005) has inspired several recent advances in data-stream algorithms. We show that a number of these results follow eas- ily from the application of a single probabilistic method called Precision Sampling. Using this method, we obtain simple data- stream algorithms that maintain a randomized sketch of an input vector x = (x1,x2,...,xn), which is useful for the following applications: 1) Estimating the Fk-moment of x, for k >; 2. 2) Estimating the ℓp-norm of x, for p ϵ [1, 2], with small update time. 3) Estimating cascaded norms ℓp(ℓq) for all p,q >; 0. 4) ℓ1sampling, where the goal is to produce an element i with probability (approximately) |xi|/||x||1. It extends to similarly defined ℓp-sampling, for p ϵ [1, 2]. For all these applications the algorithm is essentially the same: scale the vector x entry-wise by a well-chosen random vector, and run a heavy-hitter estimation algorithm on the resulting vector. Our sketch is a linear function of x, thereby allowing general updates to the vector x. Precision Sampling itself addresses the problem of estimating a sum Σi=1naifrom weak estimates of each real aiϵ [0,1]. More precisely, the estimator first chooses a desired precision uiϵ (0,1] for each i ϵ [n], and then it receives an estimate of every aiwithin additive ui. Its goal is to provide a good approximation to Σaiwhile keeping a tab on the "approximation cost" Σi(1/ui)- Here we refine previous work (Andoni, Krauthgamer, and Onak, FOCS 2010) which shows that as long as Σai= Ω(1), a good multiplicative approximation can be achieved using total precision of only O(n log n).

We present a near-linear time algorithm that approximates the edit distance between two strings within a polylogarithmic factor. For strings of length n and every fixed ε >; 0, the algorithm computes a (log n)O(1/ε)approximation in n1+εtime. This is an exponential improvement over the previously known approximation factor, 2Õ(√log n), with a comparable running time [Ostrovsky and Rabani, J. ACM 2007; Andoni and Onak, STOC 2009]. This result arises naturally in the study of a new asymmetric query model. In this model, the input consists of two strings x and y, and an algorithm can access y in an unrestricted manner, while being charged for querying every symbol of x. Indeed, we obtain our main result by designing an algorithm that makes a small number of queries in this model. We then provide a nearly-matching lower bound on the number of queries. Our lower bound is the first to expose hardness of edit distance stemming from the input strings being “repetitive”, which means that many of their substrings are approximately identical. Consequently, our lower bound provides the first rigorous separation between edit distance and Ulam distance.

We prove that any sketching protocol for edit distance achieving a constant approximation requires nearly logarithmic (in the strings’ length) communication complexity. This is an exponential improvement over the previous, doubly-logarithmic, lower bound of [Andoni-Krauthgamer, FOCS'07]. Our lower bound also applies to the Ulam distance (edit distance over non-repetitive strings). In this special case, it is polynomially related to the recent upper bound of [Andoni-Indyk-Krauthgamer, SODA'09]. Prom a technical perspective, we prove a direct-sum theorem for sketching product metrics that is of independent interest. We show that, for any metric X that requires sketch size which is a sufficiently large constant, sketching the max-product metric ℓd∞(X) requires Ω(d) bits. The conclusion, in fact, also holds for arbitrary two-way communication. The proof uses a novel technique for information complexity based on Poincaré inequalities and suggests an intimate connection between non-embeddability, sketching and communication complexity.

We give near-tight bounds for estimating the edit distance between two non-repetitive strings (Ulam distance) with constant approximation, in sub-linear time. For two strings of length d and at edit distance R, our algorithm runs in time and outputs a constant approximation to R. We also prove a matching lower bound (up to logarithmic terms). Both upper and lower bounds are improvements over previous results from, respectively, [Andoni-Indyk-Krauthgamer, SODA'09] and [Batu-Ergun-Kilian-Magen-Raskhodnikova-Rubinfeld-Sami, STOC'03].

We prove the first nontrivial communication complexity lower bound for the problem of estimating the edit distance (aka Levenshtein distance) between two strings. To the best of our knowledge, this is the first computational setting in which the complexity of estimating the edit distance is provably larger than that of Hamming distance. Our lower bound exhibits a trade-off between approximation and communication, asserting, for example, that protocols with $O(1)$ bits of communication can obtain only approximation $\alpha\geq\Omega(\log d/\log\log d)$, where d is the length of the input strings. This case of $O(1)$ communication is of particular importance since it captures constant-size sketches as well as embeddings into spaces like $l_1$ and squared-$l_2$, two prevailing algorithmic approaches for dealing with edit distance. Indeed, the known nontrivial communication upper bounds are all derived from embeddings into $l_1$. By excluding low-communication protocols for edit distance, we rule out a strictly richer class of algorithms than previous results. Furthermore, our lower bound holds not only for strings over a binary alphabet but also for strings that are permutations (aka the Ulam metric). For this case, our bound nearly matches an upper bound known via embedding the Ulam metric into $l_1$. Our proof uses a new technique that relies on Fourier analysis in a rather elementary way.

We provide the first sub-linear sketching algorithm for estimating the planar Earth-Mover Distance with a constant approximation. For sets living in the two-dimensional grid [¿]2, we achieve space ¿¿for approximation O(1/¿), for any desired 0 < ¿ < 1. Our sketch has immediate applications to the streaming and nearest neighbor search problems.

A common approach for solving computational problems over a difficult metric space is to embed the “hard” metric into L1, which admits efficient algorithms and is thus considered an “easy” metric. This approach has proved successful or partially successful for important spaces such as the edit distance, but it also has inherent limitations: it is provably impossible to go below certain approximation for some metrics. We propose a new approach, of embedding the difficult space into richer host spaces, namely iterated products of standard spaces like ℓ1 and ℓ∞. We show that this class is rich since it contains useful metric spaces with only a constant distortion, and, at the same time, it is tractable and admits efficient algorithms. Using this approach, we obtain for example the first nearest neighbor data structure with O(log log d) approximation for edit distance in non-repetitive strings (the Ulam metric). This approximation is exponentially better than the lower bound for embedding into L1. Furthermore, we give constant factor approximation for two other computational problems. Along the way, we answer positively a question posed in [Ajtai, Jayram, Kumar, and Sivakumar, STOC 2002]. One of our algorithms has already found applications for smoothed edit distance over 0–1 strings [Andoni and Krauthgamer, ICALP 2008].

We consider the problem of approximate nearest neighbors in high dimensions, when the queries are lines. In this problem, given n points in ℝd, we want to construct a data structure to support efficiently the following queries: given a line L, report the point p closest to L. This problem generalizes the more familiar nearest neighbor problem. From a practical perspective, lines, and low-dimensional flats in general, may model data under linear variation, such as physical objects under different lighting. For approximation 1 + ∊, we achieve a query time of d3n0.5+t, for arbitrary small t > 0, with a space of d2no(1/∊2+1/t2). To the best of our knowledge, this is the first algorithm for this problem with polynomial space and sub-linear query time.

We show how to compute the edit distance between two strings of length n up to a factor of 2(O-tilde(sqrt(log n))) in n(1+o(1)) time. This is the first sub-polynomial approximation algorithm for this problem that runs in near-linear time, improving on the state-of-the-art n(1/3+o(1)) approximation. Previously, approximation of 2O √log n) was known only for embedding edit distance into l1, and it is not known if that embedding can be computed in less than a quadratic time.

Recent years have seen a significant increase in our understanding of high-dimensional nearest neighbor search (NNS) for distances like the lscr1and lscr2norms. By contrast, our understanding of the lscrinfinnorm is now where it was (exactly) 10 years ago. In FOCSpsila98, Indyk proved the following unorthodox result: there is a data structure (in fact, a decision tree) of size O(nrho), for any rho > 1, which achieves approximation O(logrholog d) for NNS in the d-dimensional lscr1metric. In this paper, we provide results that indicate that Indykpsilas unconventional bound might in fact be optimal. Specifically, we show a lower bound for the asymmetric communication complexity of NNS under lscrinfin, which proves that this space/approximation trade-off is optimal for decision trees and for data structures with constant cell-probe complexity.

No abstract available.

We prove the first non-trivial communication complexity lower bound for the problem of estimating the edit distance (aka Levenshtein distance) between two strings. A major feature of our result is that it provides the first setting in which the complexity of computing the edit distance is provably larger than that of Hamming distance. Our lower bound exhibits a trade-off between approximation and communication, asserting, for example, thai protocols with O(1) bits of communication can only obtain approximation a ges Omega(log d/log log d), where d is the length of the input strings. This case of O(1) communication is of particular importance, since it captures constant-size sketches as well as embaddings into spaces like L1and squared-L2. two prevailing algorithmic approaches for dealing with edit distance. Furthermore, the bound holds not only for strings over alphabet Sigma= {0, 1}, but also for strings that are permu-tations (called the Ulam metric). Besides being applicable to a much richer class of algorithms than all previous results, our bounds are near-tight in at. least one case, namely of embedding permutations into L1. The proof uses a new technique, that relies on Fourier analysis in a rather elementary way.

In this work, we consider the problems of testing whether adistribution over (0,1n) is k-wise (resp. (ε,k)-wise) independentusing samples drawn from that distribution.

We present an algorithm for the c-approximate nearest neighbor problem in a d-dimensional Euclidean space, achieving query time of O(dn1c2/+o(1)) and space O(dn + n1+1c2/+o(1)). This almost matches the lower bound for hashing-based algorithm recently obtained in (R. Motwani et al., 2006). We also obtain a space-efficient version of the algorithm, which uses dn+n logO(1)n space, with a query time of dnO(1/c2). Finally, we discuss practical variants of the algorithms that utilize fast bounded-distance decoders for the Leech lattice

We investigate the optimality of (1+\in )-approximation algorithms obtained via the dimensionality reduction method. We show that: --Any data structure for the (1+\in )-approximate nearest neighbor problem in Hamming space, which uses constant number of probes to answer each query, must use n^{\Omega \left( {1/ \in ^2 } \right)} space. --Any algorithm for the (1+\in )-approximate closest substring problem must run in time exponential in 1/ \in ^{2 - \gamma } for any \gamma > 0 (unless 3SAT can be solved in subexponential time) Both lower bounds are (essentially) tight.

When distributing digital content over a broadcast channel it's often necessary to revoke users whose access privileges have expired, thus preventing them from recovering the content. This works well when users make a conscious decision to leave the system or have misbehaved, but numerous cases exist in which the revocation is in error and users are consequently left with the often onerous burden of getting reinstated. We introduce a gradual form of revocation that we call service degradation that enables the content distributor to provide "cues" to the user in the form of degraded system performance. The cues alert the user to their impending revocation and allow them to take the necessary action to remain in the system. Our protocols build on techniques for broadcast encryption and spam-fighting to provide the appropriate form of service for this previously ignored class of users.