Erik Waingarten

FOCS Conference 2025 Conference Paper

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams

• Sanjeev Khanna
• Ashwin Padaki
• Krish Singal
• Erik Waingarten

We study the space complexity of estimating the diameter of a subset of points in an arbitrary metric space in the dynamic (turnstile) streaming model. The input is given as a stream of updates to a frequency vector $x \in \mathbb{Z}_{\geq 0}^{n}$, where the support of x defines a multiset of points in a fixed metric space $\mathcal{M}=([n], \mathrm{d})$. The goal is to estimate the diameter of this multiset, defined as max $\left\{\mathrm{d}(i, j): x_{i}, x_{j} \gt \right. 0\}$, to a specified approximation factor while using as little space as possible. In insertion-only streams, a simple $O(\log n)$-space algorithm achieves a $\mathbf{2}$-approximation. In sharp contrast to this, we show that in the dynamic streaming model, any algorithm achieving a constant-factor approximation to diameter requires polynomial space. Specifically, we prove that a c-approximation to the diameter requires $n^{\Omega(1 / c)}$ space. Our lower bound relies on two conceptual contributions: (1) a new connection between dynamic streaming algorithms and linear sketches for scale-invariant functions, a class that includes diameter estimation, and (2) a connection between linear sketches for diameter and the minrank of graphs, a notion previously studied in index coding. We complement our lower bound with a nearly matching upper bound, which gives a c-approximation to the diameter in general metrics using $n^{O(1 / c)}$ space.

FOCS Conference 2025 Conference Paper

Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair

• Lorenzo Beretta 0001
• Vincent Cohen-Addad
• Rajesh Jayaram
• Erik Waingarten

We give a reduction from (1 + ε)-approximate Earth Mover’s Distance (EMD) to (1 + ε)-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given p ∈ [1], [2] and two sets of n points $X, Y \subset \left( {{\mathbb{R}^d}, {\ell _p}} \right)$, their EMD is the minimum cost of a perfect matching between X and Y, where the cost of matching two vectors is their ℓ p distance. Further, CP is the basic problem of finding a pair of points realizing min x∈X, y∈Y ║x − y║ p. Our contribution is twofold: • We show that if (1 + ε)-approximate CP can be computed in time n 2−ϕ, then a 1 + O(ε) approximation to EMD can be computed in time n 2−Ω(ϕ). • Plugging in the fastest known algorithm for CP [5], we obtain a (1 + ε)-approximation algorithm for EMD running in time ${n^{2 - \tilde \Omega \left( {{\varepsilon ^{1/3}}} \right)}}$ for high-dimensional point sets, which improves over the prior fastest running time of ${n^{2 - \Omega \left( {{\varepsilon ^2}} \right)}}$ [13]. Our main technical contribution is a sublinear implementation of the Multiplicative Weights Update framework for EMD. Specifically, we demonstrate that the updates can be executed without ever explicitly computing or storing the weights; instead, we exploit the underlying geometric structure to perform the updates implicitly.

FOCS Conference 2025 Conference Paper

Average Distortion Sketching

• Yiqiao Bao
• Anubhav Baweja
• Nicolas Menand
• Erik Waingarten
• Nathan White
• Tian Zhang 0009

We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwise distances. The novelty is studying average-distortion: for any fixed (yet, arbitrary) distribution $\mu$ over the metric, the sketch should not over-estimate distances, and it should (approximately) preserve the average distance with respect to draws from $\mu$. The notion generalizes average-distortion embeddings into $\ell_{1}$ [1], [2] as well as data-dependent locality-sensitive hashing [3], [4], which have been recently studied in the context of nearest neighbor search. •For all $p \in(2, \infty)$ and any c larger than a fixed constant, we give an average-distortion sketch for ($[\Delta]^{d}, \ell_{p}$) with approximation c and bit-complexity poly $\left(2^{p / c} \cdot \log (d \Delta)\right)$, which is provably impossible in (worst-case) sketching. •As an application, we improve on the approximation of sublinear-time data structures for nearest neighbor search over $\ell_{p}$ (for large $p\gt2$). The prior best approximation was $O(p)$ [2], [4], and we show it can be any c larger than a fixed constant (irrespective of p) by using $n^{O(p / c)}$ space. We give some evidence that $2^{\Omega(p / c)}$ space may be necessary by giving a lower bound on average-distortion sketches which produce a certain probabilistic certificate of farness (which our sketches crucially rely on).

FOCS Conference 2025 Conference Paper

Instance-Optimal Uniformity Testing and Tracking

• Guy Blanc
• Clément L. Canonne
• Erik Waingarten

In the uniformity testing task, an algorithm is provided with samples from an unknown probability distribution over a (known) finite domain, and must decide whether it is the uniform distribution, or, alternatively, if its total variation distance from uniform exceeds some input distance parameter. This question has received a significant amount of interest and its complexity is, by now, fully settled. Yet, we argue that it fails to capture many scenarios of interest, and that its very definition as a gap problem in terms of a prespecified distance may lead to suboptimal performance. To address these shortcomings, we introduce the problem of uniformity tracking, whereby an algorithm is required to detect deviations from uniformity (however they may manifest themselves) using as few samples as possible, and be competitive against an optimal algorithm knowing the distribution profile in hindsight. Our main contribution is a polylog(opt)-competitive uniformity tracking algorithm. We obtain this result by leveraging new structural results on Poisson mixtures, which we believe to be of independent interest.

SODA Conference 2025 Conference Paper

Lower Bounds for Convexity Testing

• Xi Chen 0001
• Anindya De
• Shivam Nadimpalli
• Rocco A. Servedio
• Erik Waingarten

STOC Conference 2025 Conference Paper

Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning

• Deeparnab Chakrabarty
• Xi Chen 0001
• Simeon Ristic
• C. Seshadhri 0001
• Erik Waingarten

We study monotonicity testing of high-dimensional distributions on {−1,1} n in the model of subcube conditioning, suggested and studied by Canonne, Ron, and Servedio and Bhattacharyya and Chakraborty. Previous work shows that the sample complexity of monotonicity testing must be exponential in n (Rubinfeld, Vasilian, and Aliakbarpour, Gouleakis, Peebles, Rubinfeld, Yodpinyanee). We show that the subcube query complexity is Θ( n /є 2 ), by proving nearly matching upper and lower bounds. Our work is the first to use directed isoperimetric inequalities (developed for function monotonicity testing) for analyzing a distribution testing algorithm. Along the way, we generalize an inequality of Khot, Minzer, and Safra to real-valued functions on {−1,1} n . We also study uniformity testing of distributions that are promised to be monotone, a problem introduced by Rubinfeld, Servedio, using subcube conditioning. We show that the query complexity is Θ(√ n /є 2 ). Our work proves the lower bound, which matches (up to poly-logarithmic factors) the uniformity testing upper bound for general distributions (Canonne, Chen, Kamath, Levi, Waingarten). Hence, we show that monotonicity does not help, beyond logarithmic factors, in testing uniformity of distributions with subcube conditional queries.

SODA Conference 2025 Conference Paper

Nearly Tight Bounds on Testing of Metric Properties

• Yiqiao Bao
• Sampath Kannan
• Erik Waingarten

ICML Conference 2025 Conference Paper

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

• Jie Gao 0001
• Rajesh Jayaram
• Benedikt Kolbe
• Shay Sapir
• Chris Schwiegelshohn
• Sandeep Silwal
• Erik Waingarten

Randomized dimensionality reduction is a widely-used algorithmic technique for speeding up large-scale Euclidean optimization problems. In this paper, we study dimension reduction for a variety of maximization problems, including max-matching, max-spanning tree, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the doubling dimension $\lambda_X$ of the underlying dataset $X$—a quantity measuring intrinsic dimensionality of point sets. Specifically, the dimension required is $O(\lambda_X)$, which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence grow with the dataset size $|X|$. We also provide empirical results validating the quality of solutions found in the projected space, as well as speedups due to dimensionality reduction.

SODA Conference 2025 Conference Paper

The Johnson-Lindenstrauss Lemma for Clustering and Subspace Approximation: From Coresets to Dimension Reduction

• Moses Charikar
• Erik Waingarten

SODA Conference 2024 Conference Paper

A Quasi-Monte Carlo Data Structure for Smooth Kernel Evaluations

• Moses Charikar
• Michael Kapralov
• Erik Waingarten

In the kernel density estimation (KDE) problem one is given a kernel K(x, y) and a dataset P of points in a high dimensional Euclidean space, and must prepare a small space data structure that can quickly answer density queries: given a point q, output a (1 + ɛ )-approximation to. The classical approach to KDE (and the more general problem of matrix vector multiplication for kernel matrices) is the celebrated fast multipole method of Greengard and Rokhlin [1983]. The fast multipole method combines a basic space partitioning approach with a multidimensional Taylor expansion, which yields a ≈ log d ( n / ɛ ) query time (exponential in the dimension d ). A recent line of work initiated by Charikar and Siminelakis [2017] achieved polynomial dependence on d via a combination of random sampling and randomized space partitioning, with Backurs et al. [2018] giving an efficient data structure with query time ≈ polylog(1/µ)/ ɛ 2 for smooth kernels. Quadratic dependence on ɛ, inherent to the sampling (i. e. , Monte Carlo) methods above, is prohibitively expensive for small ɛ. This is a classical issue addressed by quasi-Monte Carlo methods in numerical analysis. The high level idea in quasi-Monte Carlo methods is to replace random sampling with a discrepancy based approach - an idea recently applied to coresets for KDE by Phillips and Tai [2020]. The work of Phillips and Tai gives a space efficient data structure with query complexity ≈ 1/( ɛ μ). This is polynomially better in 1/ ɛ, but exponentially worse in 1/μ. In this work we show how to get the best of both worlds: we give a data structure with ≈ polylog(1 /μ)/ ɛ query time for smooth kernel KDE. Our main insight is a new way to combine discrepancy theory with randomized space partitioning inspired by, but significantly more efficient than, that of the fast multipole methods. We hope that our techniques will find further applications to linear algebra for kernel matrices.

STOC Conference 2024 Conference Paper

Data-Dependent LSH for the Earth Mover's Distance

• Rajesh Jayaram
• Erik Waingarten
• Tian Zhang 0009

NeurIPS Conference 2023 Conference Paper

Near-Linear Time Algorithm for the Chamfer Distance

• Ainesh Bakshi
• Piotr Indyk
• Rajesh Jayaram
• Sandeep Silwal
• Erik Waingarten

For any two point sets $A, B \subset \mathbb{R}^d$ of size up to $n$, the Chamfer distance from $A$ to $B$ is defined as $\texttt{CH}(A, B)=\sum_{a \in A} \min_{b \in B} d_X(a, b)$, where $d_X$ is the underlying distance measure (e. g. , the Euclidean or Manhattan distance). The Chamfer distance is a popular measure of dissimilarity between point clouds, used in many machine learning, computer vision, and graphics applications, and admits a straightforward $O(d n^2)$-time brute force algorithm. Further, Chamfer distance is often used as a proxy for the more computationally demanding Earth-Mover (Optimal Transport) Distance. However, the \emph{quadratic} dependence on $n$ in the running time makes the naive approach intractable for large datasets. We overcome this bottleneck and present the first $(1+\epsilon)$-approximate algorithm for estimating Chamfer distance with a near-linear running time. Specifically, our algorithm runs in time $O(nd \log (n)/\epsilon^2)$ and is implementable. Our experiments demonstrate that it is both accurate and fast on large high-dimensional datasets. We believe that our algorithm will open new avenues for analyzing large high-dimensional point clouds. We also give evidence that if the goal is to report a $(1+\epsilon)$-approximate mapping from $A$ to $B$ (as opposed to just its value), then any sub-quadratic time algorithm is unlikely to exist.

NeurIPS Conference 2023 Conference Paper

Simple, Scalable and Effective Clustering via One-Dimensional Projections

• Moses Charikar
• Monika Henzinger
• Lunjia Hu
• Maximilian Vötsch
• Erik Waingarten

Clustering is a fundamental problem in unsupervised machine learning with many applications in data analysis. Popular clustering algorithms such as Lloyd's algorithm and $k$-means++ can take $\Omega(ndk)$ time when clustering $n$ points in a $d$-dimensional space (represented by an $n\times d$ matrix $X$) into $k$ clusters. On massive datasets with moderate to large $k$, the multiplicative $k$ factor can become very expensive. We introduce a simple randomized clustering algorithm that provably runs in expected time $O(\mathsf{nnz}(X) + n\log n)$ for arbitrary $k$. Here $\mathsf{nnz}(X)$ is the total number of non-zero entries in the input dataset $X$, which is upper bounded by $nd$ and can be significantly smaller for sparse datasets. We prove that our algorithm achieves approximation ratio $\widetilde{O}(k^4)$ on any input dataset for the $k$-means objective, and our experiments show that the quality of the clusters found by our algorithm is usually much better than this worst-case bound. We use our algorithm for $k$-means clustering and for coreset construction; our experiments show that it gives a new tradeoff between running time and cluster quality compared to previous state-of-the-art methods for these tasks. Our theoretical analysis is based on novel results of independent interest. We show that the approximation ratio achieved after a random one-dimensional projection can be lifted to the original points and that $k$-means++ seeding can be implemented in expected time $O(n\log n)$ in one dimension.

STOC Conference 2023 Conference Paper

Streaming Euclidean MST to a Constant Factor

• Xi Chen 0001
• Vincent Cohen-Addad
• Rajesh Jayaram
• Amit Levi
• Erik Waingarten

We study streaming algorithms for the fundamental geometric problem of computing the cost of the Euclidean Minimum Spanning Tree (MST) on an n -point set X ⊂ ℝ d . In the streaming model, the points in X can be added and removed arbitrarily, and the goal is to maintain an approximation in small space. In low dimensions, (1+є) approximations are possible in sublinear space [Frahling, Indyk, Sohler, SoCG ’05]. However, for high dimensional spaces the best known approximation for this problem was Õ(log n ), due to [Chen, Jayaram, Levi, Waingarten, STOC ’22], improving on the prior O (log 2 n ) bound due to [Indyk, STOC ’04] and [Andoni, Indyk, Krauthgamer, SODA ’08]. In this paper, we break the logarithmic barrier, and give the first constant factor sublinear space approximation to Euclidean MST. For any є≥ 1, our algorithm achieves an Õ(є −2 ) approximation in n O (є) space. We complement this by proving that any single pass algorithm which obtains a better than 1.10-approximation must use Ω(√ n ) space, demonstrating that (1+є) approximations are not possible in high-dimensions, and that our algorithm is tight up to a constant. Nevertheless, we demonstrate that (1+є) approximations are possible in sublinear space with O (1/є) passes over the stream. More generally, for any α ≥ 2, we give a α-pass streaming algorithm which achieves a (1+ O (logα + 1/ α є)) approximation in n O (є) d O (1) space. All our streaming algorithms are linear sketches, and therefore extend to the massively-parallel computation model (MPC). Thus, our results imply the first (1+є)-approximation to Euclidean MST in a constant number of rounds in the MPC model. Previously, such a result was only known for low-dimensional space [Andoni, Nikolov, Onak, Yaroslavtsev, STOC ’15], or required either O (log n ) rounds or a O (log n ) approximation.

NeurIPS Conference 2022 Conference Paper

Estimation of Entropy in Constant Space with Improved Sample Complexity

• Maryam Aliakbarpour
• Andrew McGregor
• Jelani Nelson
• Erik Waingarten

Recent work of Acharya et al. ~(NeurIPS 2019) showed how to estimate the entropy of a distribution $\mathcal D$ over an alphabet of size $k$ up to $\pm\epsilon$ additive error by streaming over $(k/\epsilon^3) \cdot \text{polylog}(1/\epsilon)$ i. i. d. \ samples and using only $O(1)$ words of memory. In this work, we give a new constant memory scheme that reduces the sample complexity to $(k/\epsilon^2)\cdot \text{polylog}(1/\epsilon)$. We conjecture that this is optimal up to $\text{polylog}(1/\epsilon)$ factors.

STOC Conference 2022 Conference Paper

New streaming algorithms for high dimensional EMD and MST

• Xi Chen 0001
• Rajesh Jayaram
• Amit Levi
• Erik Waingarten

We study streaming algorithms for two fundamental geometric problems: computing the cost of a Minimum Spanning Tree (MST) of an n -point set X ⊂ {1,2,…,Δ} d , and computing the Earth Mover Distance (EMD) between two multi-sets A , B ⊂ {1,2,…,Δ} d of size n . We consider the turnstile model, where points can be added and removed. We give a one-pass streaming algorithm for MST and a two-pass streaming algorithm for EMD, both achieving an approximation factor of Õ(log n ) and using ( n , d ,Δ)-space only. Furthermore, our algorithm for EMD can be compressed to a single pass with a small additive error. Previously, the best known sublinear-space streaming algorithms for either problem achieved an approximation of O (min{ log n , log(Δ d )} log n ). For MST, we also prove that any constant space streaming algorithm can only achieve an approximation of Ω(log n ), analogous to the Ω(log n ) lower bound for EMD.

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.

SODA Conference 2021 Conference Paper

Random Restrictions of High Dimensional Distributions and Uniformity Testing with Subcube Conditioning

• Clément L. Canonne
• Xi Chen 0001
• Gautam Kamath 0001
• Amit Levi
• Erik Waingarten

We give a nearly-optimal algorithm for testing uniformity of distributions supported on {–1, 1} n, which makes many queries to a subcube conditional sampling oracle (Bhattacharyya and Chakraborty (2018)). The key technical component is a natural notion of random restrictions for distributions on {–1, 1} n, and a quantitative analysis of how such a restriction affects the mean vector of the distribution. Along the way, we consider the problem of mean testing with independent samples and provide a nearly-optimal algorithm.

SODA Conference 2020 Conference Paper

Approximating the Distance to Monotonicity of Boolean Functions

• Ramesh Krishnan S. Pallavoor
• Sofya Raskhodnikova
• Erik Waingarten

We design a nonadaptive algorithm that, given a Boolean function f: {0, 1} n → {0, 1} which is α-far from monotone, makes poly( n, 1/α) queries and returns an estimate that, with high probability, is an -approximation to the distance of f to monotonicity. Furthermore, we show that for any constant k > 0, approximating the distance to monotonicity up to n 1/2− k -factor requires nonadaptive queries, thereby ruling out a poly( n, 1/α)-query nonadaptive algorithm for such approximations. This answers a question of Seshadhri (Property Testing Review, 2014) for the case of nonadaptive algorithms. Approximating the distance to a property is closely related to tolerantly testing that property. Our lower bound stands in contrast to standard (non-tolerant) testing of monotonicity that can be done nonadaptively with queries. We obtain our lower bound by proving an analogous bound for erasure-resilient testers. An α-erasure-resilient tester for a desired property gets oracle access to a function that has at most an α fraction of values erased. The tester has to accept (with probability at least 2/3) if the erasures can be filled in to ensure that the resulting function has the property and to reject (with probability at least 2/3) if every completion of erasures results in a function that is ε -far from having the property. Our method yields the same lower bounds for unateness and being a k -junta. These lower bounds improve exponentially on the existing lower bounds for these properties.

SODA Conference 2020 Conference Paper

Nearly optimal edge estimation with independent set queries

• Xi Chen 0001
• Amit Levi
• Erik Waingarten

We study the problem of estimating the number of edges of an unknown, undirected graph G = ([ n ], E ) with access to an independent set oracle. When queried about a subset S ⊆ [ n ] of vertices, the independent set oracle answers whether S is an independent set in G or not. Our first main result is an algorithm that computes a (1 + ϵ )-approximation of the number of edges m of the graph using · poly(log n, 1/ ϵ ) independent set queries. This improves the upper bound of · poly(log n, 1/ ε ) by Beame et al. [3]. Our second main result shows that /polylog( n ) independent set queries are necessary, thus establishing that our algorithm is optimal up to a factor of poly(log n, 1/ ϵ ).

FOCS Conference 2019 Conference Paper

Finding Monotone Patterns in Sublinear Time

• Omri Ben-Eliezer
• Clément L. Canonne
• Shoham Letzter
• Erik Waingarten

We study the problem of finding monotone subsequences in an array from the viewpoint of sublinear algorithms. For fixed k ∊ N and ε > 0, we show that the non-adaptive query complexity of finding a length-k monotone subsequence of f: [n] → R, assuming that f is ε-far from free of such subsequences, is Θ((log n)^ ⌊log_2k⌋ ). Prior to our work, the best algorithm for this problem, due to Newman, Rabinovich, Rajendraprasad, and Sohler (2017), made (log n)^O(k^2) non-adaptive queries; and the only lower bound known, of Ω(log n) queries for the case k = 2, followed from that on testing monotonicity due to Ergün, Kannan, Kumar, Rubinfeld, and Viswanathan (2000) and Fischer (2004).

STOC Conference 2019 Conference Paper

Testing unateness nearly optimally

• Xi Chen 0001
• Erik Waingarten

We present an Õ( n 2/3 /є 2 )-query algorithm that tests whether an unknown Boolean function f ∶{0,1} n → {0,1} is unate (i.e., every variable is either non-decreasing or non-increasing) or є-far from unate. The upper bound is nearly optimal given the Ω( n 2/3 ) lower bound of Chen, Waingarten and Xie (2017). The algorithm builds on a novel use of the binary search procedure and its analysis over long random paths.

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.

TCS Journal 2018 Journal Article

The fewest clues problem

• Erik D. Demaine
• Fermi Ma
• Ariel Schvartzman
• Erik Waingarten
• Scott Aaronson

When analyzing the computational complexity of well-known puzzles, most papers consider the algorithmic challenge of solving a given instance of (a generalized form of) the puzzle. We take a different approach by analyzing the computational complexity of designing a “good” puzzle. We assume a puzzle maker designs part of an instance, but before publishing it, wants to ensure that the puzzle has a unique solution. Given a puzzle, we introduce the FCP (fewest clues problem) version of the problem: Given an instance to a puzzle, what is the minimum number of clues we must add in order to make the instance uniquely solvable? We analyze this question for the Nikoli puzzles Sudoku, Shakashaka, and Akari. Solving these puzzles is NP-complete, and we show their FCP versions are Σ 2 P -complete. Along the way, we show that the FCP versions of Triangle Partition, Planar 1-in-3 SAT, and Latin Square are all Σ 2 P -complete. We show that even problems in P have difficult FCP versions, sometimes even Σ 2 P -complete, though “closed under cluing” problems are in the (presumably) smaller class NP; for example, FCP 2SAT is NP-complete.

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.

STOC Conference 2017 Conference Paper

Beyond Talagrand functions: new lower bounds for testing monotonicity and unateness

• Xi Chen 0001
• Erik Waingarten
• Jinyu Xie

We prove a lower bound of Ω( n 1/3 ) for the query complexity of any two-sided and adaptive algorithm that tests whether an unknown Boolean function f :{0,1} n → {0,1} is monotone versus far from monotone. This improves the recent lower bound of Ω( n 1/4 ) for the same problem by Belovs and Blais (STOC'16). Our result builds on a new family of random Boolean functions that can be viewed as a two-level extension of Talagrand's random DNFs. Beyond monotonicity we prove a lower bound of Ω(√ n ) for two-sided, adaptive algorithms and a lower bound of Ω( n ) for one-sided, non-adaptive algorithms for testing unateness, a natural generalization of monotonicity. The latter matches the linear upper bounds by Khot and Shinkar (RANDOM'16) and by Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri (2017).

FOCS Conference 2017 Conference Paper

Boolean Unateness Testing with Õ(n 3/4 ) Adaptive Queries

• Xi Chen 0001
• Erik Waingarten
• Jinyu Xie

We give an adaptive algorithm that tests whether an unknown Boolean function f: {0, 1} n → {0, 1} is unate (i. e. every variable of f is either non-decreasing or non-increasing) or ε-far from unate with one-sided error and Õ(n 3/4 /ϵ 2 ) many queries. This improves on the best adaptive O(n/ϵ)-query algorithm from Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova and Seshadhri [1] when 1/ϵ 1/4. Combined with the Ω̃(n)query lower bound for non-adaptive algorithms with one-sided error of [2], [3], we conclude that adaptivity helps for the testing of unateness with one-sided error. A crucial component of our algorithm is a new subroutine for finding bi-chromatic edges in the Boolean hypercube called adaptive edge search.

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.