Pith. sign in

REVIEW 3 major objections 4 minor 1 cited by

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

T0 review · 3 major / 4 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read Approximate Earth Mover's Distance is no harder than approximate closest pair, and the paper proves it.

desk verdict The EMD-to-CP reduction is real and worth engaging with; the Section 8 shattering concern from our internal review is a scaling artifact, but the FindClosePairs runtime bound is overstated for φ close to 1. read the letter →

arxiv 2508.06774 v1 pith:32PLZ2UH submitted 2025-08-09 cs.DS cs.LG

Lorenzo Beretta , Vincent Cohen-Addad , Rajesh Jayaram , Erik Waingarten This is my paper · ORCID
classification cs.DScs.LG MSC 68Q2568W2068W25
keywords Earthmover'sdistanceclosestpairmultiplicativeweightsupdatesubquadraticapproximationhigh-dimensionalgeometryWassersteinrandomizedroundingtransportationproblem
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper shows that approximating the Earth Mover's Distance (EMD) between two high-dimensional point sets is no harder than approximating their closest pair. It proves a black-box reduction: if a $(1+\varepsilon)$-approximate closest-pair algorithm runs in time $n^{2-\phi}$, then a $(1+O(\varepsilon))$-approximation to EMD runs in time $n^{2-\Omega(\phi)}$. Plugging in the fastest known closest-pair algorithm yields a $(1+\varepsilon)$-approximation to EMD in time $n^{2-\tilde{\Omega}(\varepsilon^{1/3})}$, improving the previous $n^{2-\Omega(\varepsilon^2)}$ bound. The engine is a sublinear implementation of the multiplicative weights update framework, where the weight distribution is never stored or computed explicitly but sampled from implicitly through geometric structure and closest-pair calls.

What carries the argument

Multiplicative Weights Update with implicit sampling: each round's dual certificate is obtained from $\tilde{O}(n)$ samples of a distribution $\lambda_{i,j,\sigma} \propto \exp(\eta \, \sigma P_{ij}D_{ij}/C_{ij})$, and the sampling is reduced to calls to an approximate closest-pair algorithm via a fixed random rounding set $S$ that $\tau$-shatters level sets of the distance matrix. The shattering lemma (Corollary 8.2, via Lemma 8.1) is the load-bearing object: it guarantees that one random $S$ works for all rounds, enabling rejection sampling with a large pool of maximal-probability pairs.

What would settle it

Track the actual MWU state update in Section 7 ('Tracking dependencies') and count the number of distinct partitions of the pair set induced by all possible sample histories. If that count is $2^{\Omega(n)}$ rather than $2^{\tilde{O}(\sqrt{n})}$, the per-partition failure probability $\exp(-\Omega(n^{1/2+\phi/2}))$ cannot be union-bounded, and the shattering guarantee of Lemma 8.1 fails for the real state size; a single such calculation decides the central claim.

Watch

Extended reading notes

Core claim

The central claim is a fine-grained reduction: approximate EMD is essentially as easy as approximate closest pair over $\ell_p$ for $p\in[1,2]$. The authors show that any $n^{2-\phi}$-time $(1+\varepsilon)$-approximate closest-pair oracle can be converted into a $(1+O(\varepsilon))$-approximate EMD algorithm running in time $n^{2-\Omega(\phi)}$, losing only constants. This answers their motivating question affirmatively: the spanner barrier at $n^{2-O(\varepsilon)}$ can be circumvented. The proof solves the dual of the EMD linear program via multiplicative weights, with each update implemented by sampling from a distribution over pairs with weights exponential in rounded inverse distances. T

Load-bearing premise

The argument assumes that the state of the multiplicative weights algorithm after each round depends on only about $\sqrt{n}$ sampled pairs, so that the total number of possible behaviors is small enough for one fixed random rounding set to work for all rounds; if the state actually depends on about $n$ samples, the union bound in the shattering lemma fails and the subquadratic sampling argument collapses.

Editorial extensions

If this is right

  • Any future improvement to approximate closest pair in $\ell_1$ automatically improves approximate EMD, losing only constants in $\varepsilon$ and in the exponent.
  • The $(1+\varepsilon)$-approximation to high-dimensional EMD now runs in time $n^{2-\tilde{\Omega}(\varepsilon^{1/3})}$, improving the prior $n^{2-\Omega(\varepsilon^2)}$ spanner-based bound.
  • The reduction works for all $\ell_p$, $p\in[1,2]$, via embedding into $\ell_1$ with $(1+\varepsilon)$ distortion.
  • It shows the LSH-based spanner barrier at $n^{2-O(\varepsilon)}$ is not inherent to EMD, establishing a separation between spanner-based and closest-pair-based approaches.
  • The sublinear MWU template—never materializing the $n^2$ weights—can likely be reused for other optimization problems whose constraints have geometric structure.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A direct test: implement the fixed random rounding for small $n$ and compare sampling-via-rounding against exact rejection sampling; if the shattering guarantee quantitatively matches, the dependency argument is sound in practice.
  • One can extend the reduction conceptually to other transportation-type LPs whose dual constraints are pairwise distances, though the paper does not claim this.
  • The paper's runtime transfer suggests that the 'easiest' hard subproblem for EMD may be closer-pair finding, not spanner construction; this reframes which algorithmic breakthroughs would directly speed up EMD.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper gives a conditional reduction from (1+ε)-approximate Earth Mover's Distance (EMD) over (R^d, ℓ_p), p∈[1,2], to (1+ε)-approximate Closest Pair (CP) over (R^d, ℓ_1). The main theorem claims that a CP algorithm with running time n^{2−φ(ε)} implies an EMD algorithm with running time n^{2−Ω(φ(ε))}. The technical core is a sublinear implementation of the Multiplicative Weights Update (MWU) framework: the MWU distribution λ is never materialized; instead, sampling from λ is reduced through a geometric rounding scheme (fixed randomized rounding set S), retrieval of all close pairs via a CP oracle, and a shattering argument that the single set S works across all MWU rounds. Plugging in the fastest known CP algorithm of Alman–Chan–Williams yields a (1+ε)-approximation to EMD in time n^{2−Õ(ε^{1/3})}, improving the previous n^{2−Ω(ε^2)} bound of Andoni–Zhang. The paper contains detailed proofs of the MWU template (Section 6), the sampling lemmas (Section 7), and the shattering argument (Section 8), plus an appendix for aspect-ratio reduction.

Significance. If the technical gaps identified below are repaired, this would be a significant advance: it gives the first reduction from high-dimensional EMD to CP, bypasses the spanner-based barrier, and improves the exponent in ε from ε^2 to ε^{1/3}. The paper's strengths are its modular structure, the explicit treatment of dependencies in the randomized rounding scheme, and the care taken in separating the MWU analysis from the sampling subroutines. The main theorems are not machine-checked, but the proofs are detailed and the claimed application to [ACW16] is plausible. However, the formal statement of the reduction is currently overclaimed for CP algorithms with φ close to 1, and the shattering corollary requires some technical reconciliation before the proof is fully rigorous. These issues are local rather than fatal to the main application, but they are load-bearing for the theorem as stated.

major comments (3)
  1. [Section 7.1, proof of Lemma 7.3 (final paragraph); used in Theorems 5 and 6] The claimed runtime bound Õ(n^{2−Ω(ϕ)}) does not follow from the displayed calculation. With z=n^{(1+ϕ)/2}, the SubsCP calls cost Õ(z^2)·(n/z)^{2−ϕ}=n^{1+ϕ}·n^{(1−ϕ)(2−ϕ)/2}=n^{2−(ϕ−ϕ^2)/2}, i.e., n^{2−Ω(ϕ(1−ϕ))}, not n^{2−Ω(ϕ)}. The exhaustive loop over F costs O(z·n)=n^{2−(1−ϕ)/2}, which also vanishes as ϕ→1. Hence the statement of Theorem 5 overclaims the reduction for CP algorithms with ϕ close to 1. The concrete application to [ACW16] has ϕ=Õ(ε^{1/3}) small, so it is unaffected, but the theorem should be restated with a gap of Ω(ϕ(1−ϕ)), or with ϕ restricted away from 1.
  2. [Section 8, Corollary 8.2 and Lemma 8.1] The 'follows immediately' from Lemma 8.1 needs reconciliation. Lemma 8.1's g_i returns a set of size at most t, while Corollary 8.2's Z_i is a multiset of Õ(n) samples; if the next state depends on multiplicities, the number of histories is the number of multisets, which for |A|=n^2 and t=Õ(n) is 2^{Õ(n log n)}, not 2^{Õ(√N)}. This is still dominated by the per-partition failure probability exp(−Ω(n^{1+3ϕ/8})) (since mτ/|A| = n^{1+3ϕ/8}), so the shattering conclusion is repairable. Also, applying Lemma 8.1 with |A|=n^2 and |S|=n^{2−ϕ/8} gives τ=n^{1+ϕ/4}, not the stated n^{1+ϕ/2}; a smaller τ gives a stronger shattering guarantee, so the desired conclusion follows, but the proof should say so explicitly. The apparent discrepancy about t=Õ(n) versus t=Õ(√n) is a scaling artifact: with |A|=n^2, the Lemma's t=Õ(√|A|) is exactly Õ(n).
  3. [Section 7.2, Lemma 7.9 and notation L_t] The notation L_t is overloaded: Definition 7.1 defines L_t as a level set, while immediately before Lemma 7.3 the text defines the prefix set L_t = ⋃_{j≤t} L_j. Lemma 7.9 uses both meanings in the same proof (e.g., T = L_t ∪ (S∩(L_{t+1}∪L_{t+2})) and later S∩L_{t+3}). This makes it hard to verify the claimed C_{ij}≥(1+ε)^t for pairs in the complement of T. The proof is likely correct, but the notation should be disambiguated (e.g., L_{≤t} for prefixes).
minor comments (4)
  1. [Section 5, Claim 5.7] The sentence 'The upper bound, EMD_X(b) ≤ EMD_Y(b), occurs with probability 1' should read 'lower bound'; the proof then correctly proves the upper bound EMD_Y(b) ≤ (1+O(ε log Φ))EMD_X(b).
  2. [Section 6.3, proof of Theorem 5] The proof says 'we can run an exponential search ... Then polylog(n d ε^{-1}) steps of binary search suffice.' Exponential search and binary search are different; please clarify the search scheme.
  3. [Section 7.2, Lemma 7.10] Definition 6.6 defines D with entries in {0}∪{(1+χ)^h : h∈Z_{≥0}}, but Lemma 7.10 writes s∈Z∩[−T,T] for the exponent. Since α,β are integral, nonzero |α_i−β_j|≥1, so nonnegative exponents suffice; please align the ranges.
  4. [Throughout] There are several small typos and inconsistencies, e.g., 'Theorem 5' is both the informal main theorem and the formal theorem in Section 6.3, and Lemma 5.4's proof refers to 'T_ℓ ⊆ T' when a level ℓ is meant. A careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the EMD-to-CP reduction is conditional and self-contained; cited self-work is used as an independent black box.

full rationale

The central claim is a conditional reduction: Theorem 5 assumes an external (1+ε)-approximate closest-pair oracle with running time n^{2−φ} and derives an EMD approximation in n^{2−Ω(φ)}. No quantity in the construction—rounded distances C(S), dual variables (α,β), MWU weights, or the sampling distribution λ—is defined in terms of the EMD value being computed; the EMD value enters only as the object certified through Claim 6.3. The random rounding set S is sampled uniformly without seeing the data and is not fitted to the EMD output. The only overlapping-author citations are [BT24] for weighted-sum estimation and [BR24] as contextual prior work. [BT24] is used in Lemma 7.9/7.10 to approximate normalization constants; it is an external, parameter-free prior result whose stated assumptions do not include the target EMD theorem, so it does not make the derivation circular. The paper's acknowledged technical risk is different: the reader correctly notes potential internal correctness gaps. In particular, Lemma 7.3's final exhaustive-search bound O(n^{(3+φ)/2}) is not n^{2−Ω(φ)} uniformly as φ→1, and Section 8's union bound in Lemma 8.1 appears to undercount the number of sample-history states (the MWU state depends on Õ(n) samples, while the lemma uses t=Õ(√n)). These are potential bugs in the proof of the claimed exponent, not instances of a prediction reducing to its inputs by construction or of a conclusion being imported via self-citation. Accordingly, the circularity score is 0.

Assumptions & free parameters 5 free parameters · 5 assumptions · 0 invented entities

The paper introduces no new physical or mathematical entities. Its free parameters are algorithmic constants chosen in the analysis. The main axiomatic burden is the correctness of the randomized rounding shattering argument, which appears unsupported as written.

free parameters (5)
  • φ(ε)
    The assumed exponent in the CP running time n^{2-φ(ε)}; this is an input assumption of the reduction, not fitted.
  • S size n^{2-φ/8}
    The size of the random rounding set is chosen by the authors to balance rounding granularity and running time.
  • Rounding parameter χ = γ_gap/(100 R K)
    Set to control the error from rounding the dual variables in the MWU analysis.
  • Gap parameter γ_gap = ε D_l/(2h)
    Set so that the Certify oracle detects a constant-factor gap in the tree-level condition.
  • K = D_u D_T
    Bound on the magnitude of dual variables, derived from the tree distortion parameters.
assumptions (5)
  • standard math For any p∈[1,2], ℓ_p^d embeds into ℓ_1^{d'} with (1+ε) distortion for d'=O(d log(1/ε)/ε^2) [JS82].
    Used at the start of Section 4 to justify restricting the paper to ℓ_1.
  • standard math Probabilistic tree embedding of (R^d, ℓ_1) with expected distortion O(log Φ) exists [AIK08].
    Basis for the Bi-Lipschitz quadtree construction in Section 5.
  • standard math Multiplicative Weights Update framework converges with the stated parameter choices.
    Standard analysis used in Section 6 to prove Lemma 6.8.
  • ad hoc to paper Lemma 8.1's union bound holds with t=Õ(√n) samples per state update.
    This is the load-bearing shattering assumption; it appears inconsistent with the actual Õ(n) sample dependence in Corollary 8.2.
  • domain assumption Existence of a (1+ε)-approximate CP algorithm with running time n^{2-φ} and success probability 2/3.
    The main theorem is conditional on this oracle, as stated in Theorem 1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair." pith.science (2026). https://pith.science/paper/32PLZ2UH

@misc{pith2026250806774,
  author       = {Pith},
  title        = {Pith review of: Approximating High-Dimensional Earth Mover's Distance as Fast as Closest Pair},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/32PLZ2UH}},
  note         = {Machine review of arXiv:2508.06774}
}
abstract

We give a reduction from $(1+\varepsilon)$-approximate Earth Mover's Distance (EMD) to $(1+\varepsilon)$-approximate Closest Pair (CP). As a consequence, we improve the fastest known approximation algorithm for high-dimensional EMD. Here, given $p\in [1, 2]$ and two sets of $n$ points $X,Y \subseteq (\mathbb R^d,\ell_p)$, their EMD is the minimum cost of a perfect matching between $X$ and $Y$, where the cost of matching two vectors is their $\ell_p$ distance. Further, CP is the basic problem of finding a pair of points realizing $\min_{x \in X, y\in Y} ||x-y||_p$. Our contribution is twofold: we show that if a $(1+\varepsilon)$-approximate CP can be computed in time $n^{2-\phi}$, then a $1+O(\varepsilon)$ approximation to EMD can be computed in time $n^{2-\Omega(\phi)}$; plugging in the fastest known algorithm for CP [Alman, Chan, Williams FOCS'16], we obtain a $(1+\varepsilon)$-approximation algorithm for EMD running in time $n^{2-\tilde{\Omega}(\varepsilon^{1/3})}$ for high-dimensional point sets, which improves over the prior fastest running time of $n^{2-\Omega(\varepsilon^2)}$ [Andoni, Zhang FOCS'23]. 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.

Figures

Figures reproduced from arXiv: 2508.06774 by the authors.

Figure 1
Figure 1. Linear program for EMD. Our goal will be to approximate the optimal objective value to this LP in subquadratic time. However, notice that the primal formulation has n 2 variables, in the form of the flows tγij ui,jPrns . Thus, we cannot even write down a solution to the primal, let alone directly implement iterative update methods. On the other hand, the dual has only 2n variables tαi , βiuiPrns . Thus, in principle… view at source ↗
Figure 2
Figure 2. The algorithm Embed-and-Perturb which receives a set of vectors X, and produces a perturbed set of vectors and a bi-Lipschitz tree embedding for the perturbed vectors. • E2: We consider a fixed vector b P V , and we let γ P R nˆn ě0 be the flow which realizes EMDXpbq. This event depends on the draw of T „ T from Lemma 5.3, and occurs whenever ÿn i“1 ÿn j“1 γij ¨ dTpi, jq ď O plog Φq ¨ EMDXpbq. From Lemma 5.3 and Mar… view at source ↗
Figure 3
Figure 3. The certification oracle task for each iteration. [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figures from the paper (5 more)
Figure 4
Figure 4. Figure 4: The Multiplicative Weights Update Rule. Lemma 6.8. Run the multiplicative weights algorithm in [PITH_FULL_IMAGE:figures/full_fig_p027_4.png]
Figure 5
Figure 5. Figure 5: Implementation of SubsCP. 31 [PITH_FULL_IMAGE:figures/full_fig_p032_5.png]
Figure 6
Figure 6. Figure 6: Implementation of LastSmallPrefix. Lemma 7.5. Fix z P r? n, ns. Let t “ LastSmallPrefixpX, Y, zq, then |Lt`3| ě z 2 log3 Φ and |Lt`2| ď 0.1 ¨ z 2 , with probability 1 ´ op1q. Proof. For any s “ 1 . . . ε´1 ¨ log Φ, if |Ls| ă z 2 log3 Φ we have PrrLs X S ‰ Hs ď ÿ px,yqP…
Figure 7
Figure 7. Figure 7: Implementation of FindClosePairs. Throughout, fix z “ ? n1`ϕ and t as in FindClosePairs and condition on the high-probability event in Lemma 7.5. Consider the bipartite graph G “ pX Y Y,Lt`1q. We say that a vertex x P X Y Y is light if degLt`1 pxq ď 0.5 ¨ z, and heavy …
Figure 8
Figure 8. Figure 8: Partitioning Qs . We start by proving that our algorithm outputs a partition. First, we observe that for each s P t˝u Y r´T, Ts our algorithm partitions the elements of Qs between E and several sets Iℓ ˆ Jℓ. Indeed, for s “ 0 this is trivial. For s P r´T, Ts, we notice…

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. PiPNN: Ultra-Scalable Graph-Based Nearest Neighbor Indexing

    cs.DB 2026-02 conditional novelty 6.0 of 10

    PiPNN builds high-quality approximate-nearest-neighbor search graphs up to 12.9x faster than HNSW and 11.6x faster than Vamana by replacing search-based construction with overlapping partitions, dense GEMM distance co...

Reference graph

Works this paper leans on

20 extracted references · 18 canonical work pages · cited by 1 Pith paper

  1. [1]

    Polynomial Representations of Threshold Functions with Applications

    [ACW16] Josh Alman, Timothy M. Chan, and Ryan Williams. “Polynomial Representations of Threshold Functions with Applications”. In: Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’2016) . To appear

    work page 2016

  2. [8]

    New streaming algo- rithms for high dimensional EMD and MST

    [Che+22b] Xi Chen, Rajesh Jayaram, Amit Levi, and Erik Waingarten. “New streaming algo- rithms for high dimensional EMD and MST”. In: Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing . 2022, pp. 222–233. [Cla87] Ken Clarkson. “Approximation algorithms for shortest path motion planning”. In: Proceedings of the nineteenth annual AC...

    work page 2022

  3. [9]

    Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality

    [HIM12] Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani. “Approximate Nearest Neighbor: Towards Removing the Curse of Dimensionality”. In: Theory of Computing 8.1 (2012), pp. 321–350. [HIS13] Sariel Har-Peled, Piotr Indyk, and Anastasios Sidiropoulos. “Euclidean spanners in high dimensions”. In: Proceedings of the 24th ACM-SIAM Symposium on Discrete Alg...

    work page 2012

  4. [12]

    Preconditioning and Locality in Algorithm Design

    Chicago, IL, USA: Association for Computing Machinery, 2020, pp. 308–321. isbn: 9781450369794. doi: 10.1145/3357713.3384268 . url: https://doi.org/10.1145/ 3357713.3384268. [Li21] Jason Li. “Preconditioning and Locality in Algorithm Design.” PhD thesis. Carnegie Mellon University, USA,

    work page arXiv 2020

  5. [18]

    Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem

    [Val15] Gregory Valiant. “Finding Correlations in Subquadratic Time, with Applications to Learning Parities and the Closest Pair Problem”. In: Journal of the ACM 62.2 (2015), p

    work page 2015

  6. [20]

    2023, pp

    Schloss Dagstuhl–Leibniz-Zentrum f¨ ur Informatik. 2023, pp. 104–1. 46

    work page 2023

  7. [1268]

    A near-linear time ε-approximation algo- rithm for geometric bipartite matching

    [SA12] R Sharathkumar and Pankaj K Agarwal. “A near-linear time ε-approximation algo- rithm for geometric bipartite matching”. In: Proceedings of the forty-fourth annual ACM symposium on Theory of computing . 2012, pp. 385–394. [SA20] R. Sharathkumar and Pankaj K. Agarwal. “A near- ε-approximation algorithm for bipartite geometric matching”. In: Journal o...

    work page 2012

  8. [1991]

    On a greedy heuristic for complete match- ing

    1991, pp. 207–210. [RT81] Edward M Reingold and Robert E Tarjan. “On a greedy heuristic for complete match- ing”. In: SIAM Journal on Computing 10.4 (1981), pp. 676–681. [Rub18] Aviad Rubinstein. “Hardness of approximate nearest neighbor search”. In: Proceedings of the 50th annual ACM SIGACT symposium on theory of computing . 2018, pp. 1260–

    work page 1991

Show all 20 references
  1. [2003]

    Embedding lpm into l 1 n

    [JS82] William B Johnson and Gideon Schechtman. “Embedding lpm into l 1 n”. In: Acta Mathematica 149 (1982), pp. 71–85. [KNP19] Andrey Boris Khesin, Aleksandar Nikolov, and Dmitry Paramonov. “Preconditioning for the geometric transportation problem”. In: Proceedings of the 35t...

    1982

  2. [2008]

    On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity

    [Wil18] Ryan Williams. “On the difference between closest, furthest, and orthogonal pairs: Nearly-linear vs barely-subquadratic complexity”. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms . SIAM. 2018, pp. 1207–1215. [Zuz23] Goran Zuzic. “...

    2018

  3. [2009]

    Optimal Data-Dependent Hashing for Ap- proximate Near Neighbors

    [AR15] Alexandr Andoni and Ilya Razenshteyn. “Optimal Data-Dependent Hashing for Ap- proximate Near Neighbors”. In: Proceedings of the 47th ACM Symposium on the The- ory of Computing (STOC ’2015) . Available as arXiv:1501.01062. 2015, pp. 793–801. [AS14] Pankaj K Agarwal and R...

    2015 arXiv

  4. [2013]

    Approximate Nearest Neighbors: Towards Remov- ing the Curse of Dimensionality

    [IM98] Piotr Indyk and Rajeev Motwani. “Approximate Nearest Neighbors: Towards Remov- ing the Curse of Dimensionality”. In: Proceedings of the 30th ACM Symposium on the Theory of Computing (STOC ’1998) . 1998, pp. 604–613. [Ind01] Piotr Indyk. “High-Dimensional Computational G...

    1998

  5. [2015]

    Nearly maximum flows in nearly linear time

    [She13] Jonah Sherman. “Nearly maximum flows in nearly linear time”. In: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science . IEEE. 2013, pp. 263–269. [She17] Jonah Sherman. “Generalized preconditioning and undirected minimum cost flow”. In: Proceedings of the ...

    2013

  6. [2016]

    Faster algorithms for the geometric transportation problem

    [Aga+17] Pankaj Agarwal, Kyle Fox, Debmalya Panigrahi, Kasturi Varadarajan, and Allen Xiao. “Faster algorithms for the geometric transportation problem”. In: Proceedings of the 33rd International Symposium on Computational Geometry (SOCG ’2017)

    2017

  7. [2017]

    Deter- ministic, near-linear ε-approximation algorithm for geometric bipartite matching

    [Aga+22] Pankaj K Agarwal, Hsien-Chih Chang, Sharath Raghvendra, and Allen Xiao. “Deter- ministic, near-linear ε-approximation algorithm for geometric bipartite matching”. In: Proceedings of the 54nd ACM Symposium on the Theory of Computing (STOC ’2022)

    2022

  8. [2019]

    Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs

    [RR98] Y. Rabinovich and R. Raz. “Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs”. In: Discrete & Computational Geometry 19.1 (Jan. 1, 1998), pp. 79–94. doi: 10.1007/PL00009336. url: https://doi.org/10.1007/PL00009336. [RS91] Jim Ruppert and Raimund...

    1998 doi

  9. [2020]

    Parallel approximate undirected shortest paths via low hop emulators

    Chicago, IL, USA: As- sociation for Computing Machinery, 2020, pp. 322–335. isbn: 9781450369794. doi: 10.1145/3357713.3384321. url: https://doi.org/10.1145/3357713.3384321. [ASZ20b] Alexandr Andoni, Clifford Stein, and Peilin Zhong. “Parallel approximate undirected shortest pa...

    2020

  10. [2021]

    Computational Optimal Transport: With Appli- cations to Data Science

    [PC19] Gabriel Peyr´ e and Marco Cuturi. “Computational Optimal Transport: With Appli- cations to Data Science”. In: Foundations and Trends® in Machine Learning 11.5–6 (2019), pp. 355–607. 45 [PS89] David Peleg and Alejandro A Sch¨ affer. “Graph spanners”. In: Journal of graph...

    2019

  11. [2022]

    Eu- clidean minimum spanning trees and bichromatic closest pairs

    [Aga+90] Pankaj K Agarwal, Herbert Edelsbrunner, Otfried Schwarzkopf, and Emo Welzl. “Eu- clidean minimum spanning trees and bichromatic closest pairs”. In: Proceedings of the sixth annual symposium on Computational geometry . 1990, pp. 203–210. 43 [AI08] Alexandr Andoni and P...

    1990

  12. [2023]

    Similarity estimation techniques from rounding algorithms

    [Cha02] Moses Charikar. “Similarity estimation techniques from rounding algorithms”. In: Pro- ceedings of the 34th ACM Symposium on the Theory of Computing (STOC ’2002) . 2002, pp. 380–388. 44 [Che+22a] Li Chen, Rasmus Kyng, Yang P. Liu, Richard Peng, Maximilian Probst Gutenbe...

    2002

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.