Alexandr Andoni

STOC Conference 2025 Conference Paper

A Framework for Building Data Structures from Communication Protocols

• Alexandr Andoni
• Shunhua Jiang
• Omri Weinstein

We present a general framework for designing efficient data structures for high-dimensional pattern-matching problems (∃ i ∈ [ 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 ⋆’s in the query is at most w = c log n (≪ d ), the fastest known linear-space data structure (Cole, Gottlieb and Lewenstein, STOC’04) had query time t ≈ 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 Θ(√ 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 Õ(√ 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.

FOCS Conference 2025 Conference Paper

Embeddings into Similarity Measures for Nearest Neighbor Search

• Alexandr Andoni
• Negev Shekel Nosatzki

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).

NeurIPS Conference 2025 Conference Paper

Fast attention mechanisms: a tale of parallelism

• Jingwen Liu
• Hantao Yu
• Clayton Sanford
• Alexandr Andoni
• Daniel Hsu

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.

NeurIPS Conference 2024 Conference Paper

Statistical-Computational Trade-offs for Density Estimation

• Anders Aamand
• Alexandr Andoni
• Justin Y. Chen
• Piotr Indyk
• Shyam Narayanan
• Sandeep Silwal
• Haike Xu

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.

ICML Conference 2023 Conference Paper

Data Structures for Density Estimation

• Anders Aamand
• Alexandr Andoni
• Justin Y. Chen
• Piotr Indyk
• Shyam Narayanan
• Sandeep Silwal

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.

NeurIPS Conference 2023 Conference Paper

Differentially Private Approximate Near Neighbor Counting in High Dimensions

• Alexandr Andoni
• Piotr Indyk
• Sepideh Mahabadi
• Shyam Narayanan

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.

FOCS Conference 2023 Conference Paper

Sub-quadratic (1+ϵ)-approximate Euclidean Spanners, with Applications

• Alexandr Andoni
• Hengjie Zhang

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)}$.

FOCS Conference 2022 Conference Paper

Estimating the Longest Increasing Subsequence in Nearly Optimal Time

• Alexandr Andoni
• Negev Shekel Nosatzki
• Sandip Sinha
• Cliff Stein 0001

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.

ICML Conference 2022 Conference Paper

Learning to Hash Robustly, Guaranteed

• Alexandr Andoni
• Daniel Beaglehole

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.

SODA Conference 2021 Conference Paper

Approximate Nearest Neighbors Beyond Space Partitions

• Alexandr Andoni
• Aleksandar Nikolov
• Ilya P. Razenshteyn
• Erik Waingarten

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.

FOCS Conference 2020 Conference Paper

Edit Distance in Near-Linear Time: it's a Constant Factor

• Alexandr Andoni
• Negev Shekel Nosatzki

We present an algorithm for approximating the edit distance between two strings of length n in time n 1+ε, for any, up to a constant factor. Our result completes a research direction set forth in the recent breakthrough paper [1], which showed the first constant-factor approximation algorithm with a (strongly) sub-quadratic running time. The recent results [2], [3] have shown near-linear complexity only under the restriction that the edit distance is close to maximal (equivalently, there is a near-linear additive approximation). In contrast, our algorithm obtains a constant-factor approximation in near-linear running time for any input strings.

STOC Conference 2020 Conference Paper

Parallel approximate undirected shortest paths via low hop emulators

• Alexandr Andoni
• Cliff Stein 0001
• Peilin Zhong

We present a (1+ε)-approximate parallel algorithm for computing shortest paths in undirected graphs, achieving poly (log n ) depth and m poly (log n ) 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 (log n ) 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 develop several new tools of independent interest. One of them is a new notion beyond hopsets — low hop emulator — a poly (log n )-approximate emulator graph in which every shortest path has at most O (loglog n ) hops (edges). Direct applications of the low hop emulators are parallel algorithms for poly (log n )-approximate single source shortest path (SSSP), Bourgain’s embedding, metric tree embedding, and low diameter decomposition, all with poly (log n ) depth and m poly (log n ) work. To boost the approximation ratio to (1+ε), we introduce compressible preconditioners and apply it inside Sherman’s framework (SODA’17) to solve the more general problem of uncapacitated minimum cost flow (a.k.a., transshipment problem). Our algorithm computes a (1+ε)-approximate uncapacitated minimum cost flow in poly (log n ) depth using m poly (log n ) work. As a consequence, it also improves the state-of-the-art sequential running time from m · 2 O (√log n ) to m poly (log n ).

STOC Conference 2018 Conference Paper

Data-dependent hashing via nonlinear spectral gaps

• Alexandr Andoni
• Assaf Naor
• Aleksandar Nikolov
• Ilya P. Razenshteyn
• Erik Waingarten

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: * For _general_ d -dimensional normed spaces and n -point datasets, we obtain a _cell-probe_ ANN data structure with approximation O (log d /ε 2 ), space d O (1) n 1+ε , and d O (1) n ε cell probes per query, for any ε>0. No non-trivial approximation was known before in this generality other than the O (√ d ) bound which follows from embedding a general norm into ℓ 2 . * For ℓ p and Schatten- p norms, we improve the data structure further, to obtain approximation O ( p ) and sublinear query _time_. For ℓ p , this improves upon the previous best approximation 2 O ( p ) (which required polynomial as opposed to near-linear in n space). For the Schatten- p norm, no non-trivial ANN data structure was known before this work. Previous approaches to the ANN problem either exploit the low dimensionality of a metric, requiring space exponential in the dimension, or circumvent the curse of dimensionality by embedding a metric into a ”tractable” space, such as ℓ 1 . Our new generic reduction proceeds differently from both of these approaches using a novel partitioning method.

FOCS Conference 2018 Conference Paper

Hölder Homeomorphisms and Approximate Nearest Neighbors

• Alexandr Andoni
• Assaf Naor
• Aleksandar Nikolov
• Ilya P. Razenshteyn
• Erik Waingarten

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.

FOCS Conference 2018 Conference Paper

Parallel Graph Connectivity in Log Diameter Rounds

• Alexandr Andoni
• Zhao Song 0002
• Cliff Stein 0001
• Zhengyu Wang
• Peilin Zhong

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.

ICML Conference 2018 Conference Paper

Subspace Embedding and Linear Regression with Orlicz Norm

• Alexandr Andoni
• Chengyu Lin 0001
• Ying Sheng 0004
• Peilin Zhong
• Ruiqi Zhong

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.

STOC Conference 2017 Conference Paper

Approximate near neighbors for general symmetric norms

• Alexandr Andoni
• Huy L. Nguyen 0001
• Aleksandar Nikolov
• Ilya P. Razenshteyn
• Erik Waingarten

We show that every symmetric normed space admits an efficient nearest neighbor search data structure with doubly-logarithmic approximation. Specifically, for every n , d = n o (1) , and every d -dimensional symmetric norm ||·||, there exists a data structure for (loglog n )-approximate nearest neighbor search over ||·|| for n -point datasets achieving n o (1) query time and n 1+ 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. We also show that our techniques cannot be extended to general norms.

SODA Conference 2017 Conference Paper

LSH Forest: Practical Algorithms Made Theoretical

• Alexandr Andoni
• Ilya P. Razenshteyn
• Negev Shekel Nosatzki

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].

SODA Conference 2017 Conference Paper

Optimal Hashing-based Time-Space Trade-offs for Approximate Near Neighbors

• Alexandr Andoni
• Thijs Laarhoven
• Ilya P. Razenshteyn
• Erik Waingarten

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 n 1+ ρu + o (1) + O ( dn ) and query time n ρq + o (1) + dn o (1) for every ρ u, ρ q ≥ 0 with: In particular, for the approximation c = 2 we get: Space n 1. 77… and query time n o (1), significantly improving upon known data structures that support very fast queries [IM98, KOR00]; Space n 1. 14… and query time n 0. 14…, matching the optimal data-dependent Locality-Sensitive Hashing (LSH) from [AR15]; Space n 1+ o (1) and query time n 0 ‘ 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.

STOC Conference 2015 Conference Paper

Optimal Data-Dependent Hashing for Approximate Near Neighbors

• Alexandr Andoni
• Ilya P. Razenshteyn

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(n 1+ρ+o(1) + d ⋅ n), where ρ=1/(2c 2 -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. From the technical perspective, we proceed by decomposing an arbitrary dataset into several subsets that are, in a certain sense, pseudo-random.

NeurIPS Conference 2015 Conference Paper

Practical and Optimal LSH for Angular Distance

• Alexandr Andoni
• Piotr Indyk
• Thijs Laarhoven
• Ilya Razenshteyn
• Ludwig Schmidt

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.

STOC Conference 2015 Conference Paper

Sketching and Embedding are Equivalent for Norms

• Alexandr Andoni
• Robert Krauthgamer
• Ilya P. Razenshteyn

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 l p for p∈(0,2] also admits an efficient sketching scheme. But is the converse true, i.e., is embedding into l p 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 l 1-ε with constant distortion. We further prove that for norms that are closed under sum-product, efficient sketching is equivalent to embedding into l 1 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).

SODA Conference 2014 Conference Paper

Beyond Locality-Sensitive Hashing

• Alexandr Andoni
• Piotr Indyk
• Huy L. Nguyen 0001
• Ilya P. Razenshteyn

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 O c ( n ρ + d log n ) query time and O c ( n 1+ ρ + d log n ) space, where ρ ≤ 7/(8 c 2 ) + O (1/ c 3 ) + o c (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/(8 c )+ O (1/ c 3/2 )+ o c (1), which is the first improvement over the result of Indyk and Motwani (STOC 1998).

ICML Conference 2014 Conference Paper

Learning Polynomials with Neural Networks

• Alexandr Andoni
• Rina Panigrahy
• Gregory Valiant
• Li Zhang 0001

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.

SODA Conference 2014 Conference Paper

Learning Sparse Polynomial Functions

• Alexandr Andoni
• Rina Panigrahy
• Gregory Valiant
• Li Zhang 0001

STOC Conference 2014 Conference Paper

Parallel algorithms for geometric graph problems

• Alexandr Andoni
• Aleksandar Nikolov
• Krzysztof Onak
• Grigory Yaroslavtsev

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.

FOCS Conference 2014 Conference Paper

Spectral Approaches to Nearest Neighbor Search

• Amirali Abdullah
• Alexandr Andoni
• Ravindran Kannan
• Robert Krauthgamer

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.

SODA Conference 2014 Conference Paper

Towards (1 + ∊ )-Approximate Flow Sparsifiers

• Alexandr Andoni
• Anupam Gupta 0001
• Robert Krauthgamer

A useful approach to “compress” a large network G is to represent it with a flow-sparsifier, i. e. , a small network H that supports the same flows as G, up to a factor q ≥ 1 called the quality of sparsifier. Specifically, we assume the network G contains a set of k terminals T, shared with the network H, i. e. , T ⊆ V ( G )∩ V ( H ), and we want H to preserve all multicommodity flows that can be routed between the terminals T. The challenge is to construct H that is small. These questions have received a lot of attention in recent years, leading to some known tradeoffs between the sparsifier's quality q and its size | V ( H )|. Nevertheless, it remains an outstanding question whether every G admits a flow-sparsifier H with quality q = 1 + ∊, or even q = O (1), and size | V ( H )| ≤ f ( k, ∊ ) (in particular, independent of | V ( G )| and the edge capacities). Making a first step in this direction, we present new constructions for several scenarios: Our main result is that for quasi-bipartite networks G, one can construct a (1 + ∊ )-flow-sparsifier of size poly( k / ∊ ). In contrast, exact ( q = 1) sparsifiers for this family of networks are known to require size 2 Ω ( k ). For networks G of bounded treewidth w, we construct a flow-sparsifier with quality q = O (log w /loglog w ) and size O ( w ·poly( k )). For general networks G, we construct a sketch sk ( G ), that stores all the feasible multicommodity flows up to factor q = 1 + ∊, and its size (storage requirement) is f ( k, ∊ ).

SODA Conference 2013 Conference Paper

Eigenvalues of a matrix in the streaming model

• Alexandr Andoni
• Huy L. Nguyên

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 k 2. 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.

STOC Conference 2013 Conference Paper

Homomorphic fingerprints under misalignments: sketching edit and shift distances

• Alexandr Andoni
• Assaf Goldberger
• Andrew McGregor 0001
• Ely Porat

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.

SODA Conference 2013 Conference Paper

Shift Finding in Sub-Linear Time

• Alexandr Andoni
• Piotr Indyk
• Dina Katabi
• Haitham Hassanieh

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 Õ ( N f ) 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 Õ ( n 2/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.

SODA Conference 2012 Conference Paper

Width of points in the streaming model

• Alexandr Andoni
• Huy L. Nguyên

FOCS Conference 2011 Conference Paper

Near Linear Lower Bound for Dimension Reduction in L1

• Alexandr Andoni
• Moses Charikar
• Ofer Neiman
• Huy L. Nguyên

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 ℓ 2 norm, 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/ϵ 2 dimensions. On the other hand, the only lower bounds known are that distortion δ requires n Ω(1/δ 2 ) dimensions and that distortion 1+ϵ requires n 1/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 n 1-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.

MFCS Conference 2011 Invited Paper

Nearest Neighbor Search in High-Dimensional Spaces

• Alexandr Andoni

Abstract Nearest neighbor search in high-dimensional spaces is a ubiquitous problem in searching and analyzing massive data sets. In this problem, the goal is to preprocess a set of objects (such as images), so that later, given a new query object, one can efficiently return the object most similar to the query. This problem is of key importance in several areas, including machine learning, information retrieval, image/video/music clustering, and others. For instance, it forms the basis of a widely used classification method in machine learning: to label a new object, just find a similar but already-labeled object. Nearest neighbor search also serves as a primitive for other computational problems such as closest pair, minimum spanning tree, or variants of clustering.

FOCS Conference 2011 Conference Paper

Streaming Algorithms via Precision Sampling

• Alexandr Andoni
• Robert Krauthgamer
• Krzysztof Onak

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 = (x 1, x 2, .. ., x n ), which is useful for the following applications: 1) Estimating the F k -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) ℓ 1 sampling, where the goal is to produce an element i with probability (approximately) |x i |/||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=1 n a i from weak estimates of each real a i ϵ [0, 1]. More precisely, the estimator first chooses a desired precision u i ϵ (0, 1] for each i ϵ [n], and then it receives an estimate of every a i within additive u i. Its goal is to provide a good approximation to Σa i while keeping a tab on the "approximation cost" Σ i (1/u i )- Here we refine previous work (Andoni, Krauthgamer, and Onak, FOCS 2010) which shows that as long as Σa i = Ω(1), a good multiplicative approximation can be achieved using total precision of only O(n log n).

SODA Conference 2010 Conference Paper

Lower Bounds for Edit Distance and Product Metrics via Poincaré-Type Inequalities

• Alexandr Andoni
• T. S. Jayram
• Mihai Patrascu

SODA Conference 2010 Conference Paper

Near-Optimal Sublinear Time Algorithms for Ulam Distance

• Alexandr Andoni
• Huy L. Nguyên

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].

FOCS Conference 2010 Conference Paper

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

• Alexandr Andoni
• Robert Krauthgamer
• Krzysztof Onak

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 n 1+ε 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.

SODA Conference 2009 Conference Paper

Approximate line nearest neighbor in high dimensions

• Alexandr Andoni
• Piotr Indyk
• Robert Krauthgamer
• Huy L. Nguyên

STOC Conference 2009 Conference Paper

Approximating edit distance in near-linear time

• Alexandr Andoni
• Krzysztof Onak

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 2 Õ √log n) was known only for embedding edit distance into l 1 , and it is not known if that embedding can be computed in less than a quadratic time.

FOCS Conference 2009 Conference Paper

Efficient Sketches for Earth-Mover Distance, with Applications

• Alexandr Andoni
• Khanh Do Ba
• Piotr Indyk
• David P. Woodruff

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.

SODA Conference 2009 Conference Paper

Overcoming the l 1 non-embeddability barrier: algorithms for product metrics

• Alexandr Andoni
• Piotr Indyk
• Robert Krauthgamer

SODA Conference 2008 Conference Paper

Earth mover distance over high-dimensional spaces

• Alexandr Andoni
• Piotr Indyk
• Robert Krauthgamer

FOCS Conference 2008 Conference Paper

Hardness of Nearest Neighbor under L-infinity

• Alexandr Andoni
• Dorian Croitoru
• Mihai Patrascu

Recent years have seen a significant increase in our understanding of high-dimensional nearest neighbor search (NNS) for distances like the lscr 1 and lscr 2 norms. By contrast, our understanding of the lscr infin norm 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(n rho ), for any rho > 1, which achieves approximation O(log rho log d) for NNS in the d-dimensional lscr 1 metric. 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.

STOC Conference 2007 Conference Paper

Testing k-wise and almost k-wise independence

• Noga Alon
• Alexandr Andoni
• Tali Kaufman
• Kevin Matulef
• Ronitt Rubinfeld
• Ning Xie 0002

In this work, we consider the problems of testing whether adistribution over (0,1 n ) is k -wise (resp. (ε,k)-wise) independentusing samples drawn from that distribution. For the problem of distinguishing k -wise independent distributions from those that are δ-far from k -wise independence in statistical distance, we upper bound the number ofrequired samples by Õ(n k /δ 2 ) and lower bound it by Ω(n k-1/2 /δ) (these bounds hold for constant k , and essentially the same bounds hold for general k ). Toachieve these bounds, we use Fourier analysis to relate adistribution's distance from k -wise independence to its biases, a measure of the parity imbalance it induces on a setof variables. The relationships we derive are tighter than previouslyknown, and may be of independent interest. To distinguish (ε,k)-wise independent distributions from thosethat are δ-far from (ε,k)-wise independence in statistical distance, we upper bound thenumber of required samples by O(k log n / δ 2 ε 2 ) and lower bound it by Ω(√ k log n / 2 k (ε+δ)√ log 1/2 k (ε+δ)). Although these bounds are anexponential improvement (in terms of n and k ) over thecorresponding bounds for testing k -wise independence, we give evidence thatthe time complexity of testing (ε,k)-wise independence isunlikely to be poly(n,1/ε,1/δ) for k=Θ(log n),since this would disprove a plausible conjecture concerning the hardness offinding hidden cliques in random graphs. Under the conjecture, ourresult implies that for, say, k = log n and ε = 1 / n 0.99 ,there is a set of (ε,k)-wise independent distributions, and a set of distributions at distance δ=1/n 0.51 from (ε,k)-wiseindependence, which are indistinguishable by polynomial time algorithms.

FOCS Conference 2007 Conference Paper

The Computational Hardness of Estimating Edit Distance [Extended Abstract]

• Alexandr Andoni
• Robert Krauthgamer

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 L 1 and squared-L 2. 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 L 1. The proof uses a new technique, that relies on Fourier analysis in a rather elementary way.

SODA Conference 2006 Conference Paper

Efficient algorithms for substring near neighbor problem

• Alexandr Andoni
• Piotr Indyk

FOCS Conference 2006 Conference Paper

Near-Optimal Hashing Algorithms for Approximate Nearest Neighbor in High Dimensions

• Alexandr Andoni
• Piotr Indyk

We present an algorithm for the c-approximate nearest neighbor problem in a d-dimensional Euclidean space, achieving query time of O(dn 1 c2/+o(1)) and space O(dn + n 1+1 c2/+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 log O(1) n space, with a query time of dn O(1/c2). Finally, we discuss practical variants of the algorithms that utilize fast bounded-distance decoders for the Leech lattice

FOCS Conference 2006 Conference Paper

On the Optimality of the Dimensionality Reduction Method

• Alexandr Andoni
• Piotr Indyk
• Mihai Patrascu

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.

SODA Conference 2003 Conference Paper

Lower bounds for embedding edit distance into normed spaces

• Alexandr Andoni
• Michel Deza
• Anupam Gupta 0001
• Piotr Indyk
• Sofya Raskhodnikova