Pith. sign in

REVIEW 2 major objections 5 minor 50 references

Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures

T0 review · 2 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Gaussian projections down to $O(\lambda)$ dimensions — $\lambda$ the data's doubling dimension — preserve near-optimal solutions to Euclidean maximization problems like max-matching, max-TSP and diversity measures, independent of dataset…

desk verdict Solid and genuinely new dimensionality-reduction results for Euclidean maximization and diversity problems, with a real but fixable proof gap in the main transfer theorem. read the letter →

arxiv 2506.00165 v1 pith:MBYGSJ46 submitted 2025-05-30 cs.DS cs.LG

Jie Gao , Rajesh Jayaram , Benedikt Kolbe , Shay Sapir , Chris Schwiegelshohn , Sandeep Silwal , Erik Waingarten This is my paper
classification cs.DScs.LG MSC 68W2068W2568U05
keywords randomizeddimensionalityreductiondoublingdimensionGaussianJLmapEuclideanmaximizationmaximumweightmatchingTSPdiversityTverberggraphs
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

This paper establishes that Gaussian random projections down to $O(\lambda)$ dimensions preserve near-optimal solutions to a broad family of Euclidean maximization problems, where $\lambda$ is the doubling dimension of the point set (the smallest number such that every ball can be covered by $2^\lambda$ balls of half the radius). The family covered includes maximum weight matching, maximum TSP, maximum $k$-hypermatching, maximum spanning tree, and diversity measures such as remote-clique, remote-tree, and max $k$-coverage. The target dimension is independent of the number of points, unlike classical Johnson–Lindenstrauss bounds, and it applies to every $(1+\varepsilon)$-approximate solution found in the projected space, so any algorithm chosen after projection inherits a $(1+O(\varepsilon))$ approximation in the original space. The paper also proves the dependence on $\lambda$ is necessary and identifies a sharp threshold: projecting slightly below $\Theta(\lambda)$ dimensions forces a distortion of at least $\sqrt{2}$ for matching and TSP, while distortion stays below $\sqrt{2}+\varepsilon$ all the way down to constant target dimension. Experiments on MNIST, CIFAR embeddings, and synthetic data show datasets with lower doubling dimension project much further before solution quality degrades, with up to two orders of magnitude speedup.

What carries the argument

The load-bearing mechanism is a scale-by-scale net argument over nested balls. Lemma 2.4 shows that in a maximum matching of a point set of radius $r$, all edges shorter than $r/4$ must lie inside a single ball of radius $r/2$ (otherwise swapping the pairs would increase the matching cost), so iterating produces balls $B_i$ of radius $r_i = r/2^i$ in which every matched pair has length at least $r_i/4$, and Claim 2.5, $\sum_p r_p \le 8\,\mathrm{opt}(P)$, charges the total scale mass to the optimal matching. At each level an $\varepsilon r_i$-net of size $(2/\varepsilon)^\lambda$ replaces the dataset, and two concentration facts — a stretch bound for points near net points and a norm tail bound for net-to-net distances — hold simultaneously with probability $1 - 2^{-\alpha^2}$ per level; the random variable $X = \sum_i \alpha_i |P_i| r_i$ then has expectation $O(\mathrm{opt}(P))$, making the total additive distortion $O(\varepsilon\,\mathrm{opt}(P))$ with constant probability. Secondary machinery: Tverberg graphs — a perfect matching of an even point set whose diametral balls have a common intersection — connect maximum matching to the 1-median cost with a factor $\sqrt{2}$, and the identity $\mathbb{E}|g^\top x| = \|x\|$ for a Gaussian vector $g$ makes the one-dimensional projection's matching cost an unbiased estimator of the original cost.

What would settle it

Take $P = \{e_1, \dots, e_n\} \subset \mathbb{R}^n$, the standard basis with doubling dimension $\Theta(\log n)$, project with a Gaussian JL map to $t$ with $C\varepsilon^{-2}\log(1/\varepsilon) \le t \le \log(n)/(C\log(1/\varepsilon))$, and compute the maximum matching in the projected space: Theorem 3.1 predicts a value of at least $(\sqrt{2}-\varepsilon)\cdot\mathrm{opt}(P)$ with high probability, so a value below that would refute the lower bound. To test the main transfer theorem directly, measure over many Gaussian maps at $t = O(\varepsilon^{-2}\lambda\log(1/\varepsilon))$ the fraction of trials in which the projected cost of the original optimal matching falls below $(1-\varepsilon)\mathrm{opt}(P)$; Theorem 2.1 requires that fraction to be under $1/3$, and the paper supplies no concentration estimate that implies it.

Watch

Extended reading notes

Core claim

The central claim is Theorem 2.1: for a set $P \subset \mathbb{R}^d$ with doubling dimension $\lambda$ and a Gaussian JL map $G: \mathbb{R}^d \to \mathbb{R}^t$ with $t = O(\varepsilon^{-2} \lambda \log(1/\varepsilon))$, with probability at least $2/3$ every $(1+\varepsilon)$-approximate solution computed on $G(P)$ is a $(1+O(\varepsilon))$-approximate solution on $P$, for both maximum matching and maximum TSP. The engine is Lemma 2.2, which bounds the additive distortion of any single matching by $\varepsilon \cdot \mathrm{opt}(P)$: the projected cost of every matching is at most its original cost plus a small fraction of the optimum. The proof builds nested balls of geometrically decreasing radius around matched pairs, uses nets of size $(2/\varepsilon)^\lambda$ at each level so the union bound costs $\lambda$ rather than $n$, and charges the accumulated error to the optimal matching's own cost. The same machinery transfers to $k$-hypermatching, remote subgraph diversity measures, max $k$-coverage, and max spanning tree; a separate argument via Tverberg graphs shows that without any doubling assumption a projection to $O(\varepsilon^{-2})$ dimensions already gives a $\sqrt{2}$-approximation to maximum matching, and that the $\sqrt{2}$ barrier is unavoidable in an intermediate range of target dimensions.

Load-bearing premise

The argument needs the projected cost of the optimal solution to stay within $1 \pm \varepsilon$ of its original value with high probability, but the one-line justification only rules out large upward jumps; whether the cost rarely shrinks instead is the load-bearing unproved step.

Editorial extensions

If this is right

  • Any algorithm, heuristic or exact, run on the projected data inherits the guarantee: because every $(1+\varepsilon)$-approximate solution in $\mathbb{R}^t$ is preserved, the solver can be chosen freely in the low-dimensional space and still returns a $(1+O(\varepsilon))$-approximation in $\mathbb{R}^d$.
  • One target dimension serves a family of objectives: maximum matching, maximum TSP, maximum $k$-hypermatching, maximum spanning tree, and the remote subgraph diversity measures (clique, star, tree, cycle, matching, pseudoforest, and the dispersion problem) all require only $t = O(\varepsilon^{-2}(\lambda \log(1/\varepsilon) + \log k))$.
  • The trade-off is a cliff, not a slope: reducing the target dimension below $\Theta(\lambda)$ jumps the distortion of matching and TSP optima to at least $\sqrt{2}-\varepsilon$, while above that level the distortion is $1+O(\varepsilon)$ and never worse than $\sqrt{2}+\varepsilon$ down to constant target dimension.
  • Unconditional fallbacks exist without doubling assumptions: maximum matching is $\sqrt{2}$-approximable after projection to $O(\varepsilon^{-2})$ dimensions via the 1-median bound, and maximum TSP is $(2+\varepsilon)$-approximable, so arbitrary point sets still gain from projection.

Reading between the lines

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

  • The ball-hierarchy charging argument only needs the 'short edges cluster in a ball' property of Lemma 2.4, so the same $O(\varepsilon^{-2}\lambda\log(1/\varepsilon))$ dimension should transfer to other objectives with structurally similar optima — for example maximum weight $b$-matching or budgeted diversity variants — even though the paper does not state these.
  • The upper bound carries an extra $\log(1/\varepsilon)$ factor that the $\Omega(\lambda)$ lower bound does not rule out removing; a plausible conjecture, consistent with the mechanics of the proof, is that $t = \Theta(\lambda)$ suffices and the log factor is an artifact of the level-wise union bound.
  • The paper notes it believes maximum TSP also admits a $(\sqrt{2}+\varepsilon)$-approximation in $O(\varepsilon^{-2})$ dimensions, conditional on a Tverberg-graph tour conjecture; if that conjecture holds, the unconditional $2+\varepsilon$ bound for arbitrary point sets would tighten to $\sqrt{2}+\varepsilon$.
  • The experimental protocol — comparing a dataset against a rotated low-dimensional version of itself in the same ambient dimension — gives practitioners a direct way to measure whether their data will benefit from projection before committing: if the rotated version tracks the low-$\lambda$ curve, the data's effective doubling dimension, not its ambient dimension, governs how far it can safely be c
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

2 major / 5 minor

Summary. The paper studies data-oblivious randomized dimensionality reduction for Euclidean maximization problems, including maximum matching, maximum TSP, maximum spanning tree, and several diversity measures. The main theoretical result is that for a point set of doubling dimension λ, a Gaussian JL projection to t = O(ε^{-2} λ log(1/ε)) dimensions preserves, with constant probability, every (1+ε)-approximate solution of the projected instance as a (1+O(ε))-approximate solution of the original instance for maximum matching and maximum TSP. The paper also proves lower bounds showing that Ω(λ) dimensions are necessary for these problems, exhibits a sharp √2 threshold phenomenon for maximum matching, gives a √2-approximation via a random one-dimensional projection in the general (non-doubling) case, and reports experiments comparing low- and high-intrinsic-dimensional datasets. The appendices extend the upper bounds to hypermatching, remote subgraph diversity measures, and problems with large optimal value, and provide the proofs of the lower-bound statements.

Significance. If the results are correct, this is a valuable conceptual contribution: it extends the doubling-dimension-based analysis of randomized dimensionality reduction from clustering and nearest-neighbor problems to a broad class of maximization problems, and it establishes preservation of all near-optimal solutions rather than only the optimum value. The target dimension depending on λ rather than on |X| is a genuinely useful guarantee, and the lower bounds indicate that the λ-dependence is tight. The paper also identifies an interesting sharp threshold phenomenon around dimension Θ(λ), and the Tverberg-graph argument underlying the √2-approximation for general sets is elegant. The proofs are built from established tools (Indyk–Naor ball expansion, Makarychev et al. tail bounds, LP rounding, Gaussian concentration), and the empirical section gives supporting evidence for the qualitative predictions. However, as detailed below, two load-bearing parts of the written proofs need substantial repair before the claims are rigorously established.

major comments (2)
  1. [Section 2, proof of Theorem 2.1] The lower-bound concentration step for opt(G(P)) is not justified. The text states that for an optimal solution S in P, cost(G(S)) = Σ_{e∈S} ||G u_e|| is 'w.h.p. ≥ (1−ε) Σ_{e∈S} ||u_e|| (e.g., by analyzing the expectation and applying Markov's inequality)'. Markov's inequality bounds the upper tail Pr(X ≥ a) for nonnegative X and cannot be used to lower-bound Pr(X ≥ (1−ε)E[X]). This lower-tail event is load-bearing: Lemma 2.2 only upper-bounds projected costs, so Theorem 2.1's transfer to original space requires that OPT(G(P)) does not fall below (1−ε)OPT(P). The gap is repairable — for example, F(G)=Σ_{e∈S}||G u_e|| is Lipschitz in the entries of the Gaussian matrix with constant OPT(P)/√t, so Gaussian concentration gives Pr(F ≤ E[F]−εOPT(P)) ≤ exp(−Ω(tε^2)), which with t=Ω(ε^{-2} log(1/ε)) can be made a constant success probability larger than 2/3 — but this argument is absent from the manuscript. The same issue affects the max-TSP part of Theorem 2.1 and Theorem 2.3, both of which invoke the same 'opt(G(P)) ≥ (1−ε)opt(P)' step. In addition, the probability bookkeeping should be made explicit: Lemma 2.2 holds with probability 9/10, while the lower-tail event is asserted only as 'w.h.p.', and the two need to be combined to give the stated 2/3 success probability.
  2. [Section 3, proof of Theorem 3.1] The lower-bound proof has unresolved scaling inconsistencies. The proof treats the columns Ge_i as if they were i.i.d. N(0,I_t), but by Definition 1.1 Ge_i ~ N(0, I_t/t). Lemma 3.2 and Lemma 3.3 are stated for N(0,I_t) vectors, with conclusions of the form ∥x_i∥_2/√t ∈ 1±ε and ∥x_i+y_j∥_2 ≤ ε√t. In the proof of Theorem 3.1, these lemmas are applied directly to Ge_i, and the factors of √t are then silently dropped: the text claims pairs satisfy ∥x+y∥_2 ≤ ε/100 and ∥x∥_2, ∥y∥_2 ∈ 1±ε, and concludes ∥x−y∥_2 ≥ 2−Ω(ε). If the vectors really were N(0,I_t), the distances would be about 2√t, not 2; if they are columns of the Gaussian JL map from Definition 1.1, the norms are about 1 and the event ∥x+y∥_2 ≤ ε√t has a different probability. The argument can likely be repaired by applying the lemmas to Z_i = √t Ge_i and then rescaling the resulting matching cost by 1/√t, but this rescaling is not present in the manuscript. Since Theorem 3.1 and its corollary Theorem 3.5 constitute the paper's evidence that the Ω(λ) dependence in the upper bound is tight, this is a load-bearing issue.
minor comments (5)
  1. [Lemma 2.2] The statement says 'Gaussian JL map G∈R^{d×t}'; this should be R^{t×d}, matching the target dimension t and the ambient dimension d.
  2. [Section 3, proof of Theorem 3.1] The phrase 'scaled down by 1/√d' should refer to the target dimension t, not the ambient dimension d, when describing the distribution of G e_i.
  3. [Section 3, proof of Theorem 3.1] The thresholds 'ε/100' and '1±ε' appear without the factor √t that is present in Lemmas 3.2 and 3.3, so the intended rescaling is not reconstructible from the text as written.
  4. [Theorem 3.5] The statement writes 'opt_max-tsp(GP)'; this should be 'opt_max-tsp(G(P))'.
  5. [Appendix D, Lemma D.4] The moment bound E[|S−E[S]|^m] ≤ E[S^m] is attributed to a StackExchange post (Nil, 2021); citing a standard textbook treatment of moments of nonnegative random variables would be more appropriate for a journal publication.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: Theorem 2.1 and Lemma 2.2 are derived from first-principles net arguments over external tail bounds (Indyk–Naor, Makarychev et al.); self-citations to Jiang et al. 2024 and Narayanan et al. 2021 are not load-bearing. The flagged lower-tail concentration in the proof of Theorem 2.1 rests on Markov's inequality, which is a proof gap, not a circular reduction.

full rationale

I walked the derivation chain and found no step that reduces a claimed result to its own input by construction, and no fitted parameter renamed as a prediction. The central lever, Lemma 2.2, is derived in-paper: Lemma 2.4 (ball containing all matching edges of length at most r/4) is proven from first principles via an exchange argument; Claim 2.5 sums the level radii against opt(P); Eq. (2) and Eq. (3) follow from Claim 2.6 (Makarychev et al. 2019, external) and Lemma 1.2 (Indyk–Naor 2007, external). The target dimension t = O(epsilon^-2 lambda log(1/epsilon)) emerges from the net size (2/epsilon)^lambda and union bounds, and Markov's inequality is applied correctly to the nonnegative accumulated-error variable X = sum alpha_i |P_i| r_i. The external benchmarks (Indyk–Naor ball expansion, Makarychev tail bound, Pirahmad et al. Tverberg graphs, Abbar et al. k-center packing lemma, Gupta et al. nets) are all genuinely outside the present paper's fitted values, so reliance on them is independent evidence, not circularity. The flagged weakness is real but is a correctness gap, not circularity: the proof of Theorem 2.1 asserts 'opt(G(P)) >= (1-epsilon) opt(P) w.h.p. ... (e.g., by analyzing the expectation and applying Markov's inequality)'. Markov's inequality bounds the upper tail of a nonnegative variable and cannot deliver the required lower-tail concentration for cost_G(S); Claim 2.6 is also an upper tail. A per-edge chi-square lower tail would need a union bound over n/2 edges, which the stated t does not supply, and the paper gives no second-moment argument. Without that lower bound, Lemma 2.2 alone does not complete the transfer from projected near-optimal solutions back to original space. This invalidates a load-bearing intermediate assertion (and Theorem 4.1's 'moreover' part has a similar expectation-to-high-probability step), but the claim is not equivalent to its inputs by definition or by self-citation; it is an unsupported probability assertion, which I weigh in the verdict as a proof gap, not as circularity. Self-citations are present but not load-bearing: Lemma A.6 is attributed as 'implicit in (Jiang et al., 2024)' where Jiang, Krauthgamer, and Sapir (2024) include co-author Shay Sapir, yet the paper supplies a full proof in Section A.1 using Lemma A.7 (Gupta et al., external), so the citation is provenance, not the argument. Lemma A.4 (diameter distortion lower bound) is cited to the same Jiang et al.

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

The central claims rest on standard tail bounds, the doubling-dimension covering property, and one specialized external theorem (Tverberg graph perfect matchings). No free parameters are fitted to data; all constants are universal. The paper introduces no new theoretical entities.

assumptions (5)
  • standard math For any set with doubling dimension lambda, every ball of radius R can be covered by (2/epsilon)^lambda balls of radius epsilon R (Gupta et al. 2003).
    Used in Lemma 2.2 to bound the epsilon-net size N_i <= (2/epsilon)^lambda; a standard consequence of the doubling dimension definition.
  • standard math Gaussian tail bound Pr(||Gx|| > (1+r)||x||) <= e^{-c r^2 t} for Gaussian JL matrices (Lemma 1.2 of Indyk & Naor 2007; Claim 2.6 of Makarychev et al. 2019).
    Used in Lemma 2.2 and Lemma A.6 to control distortion of net points and ball expansion.
  • domain assumption Every even point set in R^d admits a perfect matching whose diametral balls intersect (Pirahmad et al. 2024, Lemma 4.3).
    This external theorem is load-bearing for Lemma 4.2 and Theorem 4.1; the paper does not prove it.
  • standard math The LP relaxation of bipartite matching has an integral optimal solution of value at least the fractional value (Chakrabarty).
    Used in Lemma 3.4 to round the fractional matching to an integral one of comparable size.
  • standard math Chi-squared concentration bounds for norms of Gaussian vectors (Wainwright 2019).
    Used in Lemma 3.2 and the sketch for Theorem 4.1 to show most projected points have norm near 1.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures." pith.science (2026). https://pith.science/paper/MBYGSJ46

@misc{pith2026250600165,
  author       = {Pith},
  title        = {Pith review of: Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/MBYGSJ46}},
  note         = {Machine review of arXiv:2506.00165}
}
abstract

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, max TSP, as well as various measures for dataset diversity. For these problems, we show that the effect of dimension reduction is intimately tied to the \emph{doubling dimension} $\lambda_X$ of the underlying dataset $X$ -- a quantity measuring intrinsic dimensionality of point sets. Specifically, we prove that a target dimension of $O(\lambda_X)$ suffices to approximately preserve the value of any near-optimal solution,which we also show is necessary for some of these problems. This is in contrast to classical dimension reduction results, whose dependence increases 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.

Figures

Figures reproduced from arXiv: 2506.00165 by the authors.

Figure 1
Figure 1. A Tverberg graph and a point in the intersection of all disks. The angle up∗ v is not acute. min c∈Rd X p∈P ∥c − p∥ ≤ X p∈P ∥p ∗ − p∥ ≤ X {u,v}∈M∗ √ 2∥u − v∥ ≤ √ 2 max matching M X {u,v}∈M ∥u − v∥, concluding the proof. 5. Empirical Evaluation We complement our theoretical results with an empirical evaluation. Our goal is to convey two key messages: first, randomized dimensionality reduction can be very effective in… view at source ↗
Figure 2
Figure 2. Relative error versus projection dimension for maximum-matching. the vectors are dense vectors in R 6144. This is labeled Cifar-Low in our figures. • Dataset 3: Synthetic. The ‘high-intrinsic dimension’ version of this dataset consists of the n basis vectors in R n. This is labeled High Doubling Dim in our figures. The ‘low-intrinsic dimension’ version of the dataset is the cumulative sums of the basis vectors, i.e.… view at source ↗
Figure 3
Figure 3. Relative error versus projection dimension for remote-k-clique. We set k = 10 here (see [PITH_FULL_IMAGE:figures/full_fig_p022_3.png] view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Relative error versus projection dimension for remote-k-clique. We set k = 20. 10 20 30 40 50 Projection Dimension 0.2 0.4 0.6 0.8 Relative Error MNIST Max-k-Coverage, k = 10 MNIST '2' MNIST '2' + Gaussian 10 20 30 40 50 Projection Dimension 0.0 0.1 0.2 0.3 0.4 0.5 Rel…
Figure 5
Figure 5. Figure 5: Relative error versus projection dimension for max-coverage. We set k = 10. 10 20 30 40 50 Projection Dimension 0.2 0.4 0.6 0.8 Relative Error MNIST Max-k-Coverage, k = 20 MNIST '2' MNIST '2' + Gaussian 10 20 30 40 50 Projection Dimension 0.0 0.1 0.2 0.3 0.4 0.5 Relati…
Figure 6
Figure 6. Figure 6: Relative error versus projection dimension for max-coverage. We set k = 20. 23 [PITH_FULL_IMAGE:figures/full_fig_p023_6.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

50 extracted references · 34 canonical work pages

  1. [1]

    write newline

    " write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION format.date year duplicate empty "emp...

  2. [2]

    Abbar, S., Amer - Yahia, S., Indyk, P., Mahabadi, S., and Varadarajan, K. R. Diverse near neighbor problem. In Symposium on Computational Geometry, SoCG , pp.\ 207--214. ACM , 2013. doi:10.1145/2462356.2462401

    work page arXiv 2013

  3. [3]

    Nearly linear time approximation schemes for Euclidean TSP and other geometric problems

    Arora, S. Nearly linear time approximation schemes for Euclidean TSP and other geometric problems. In 38th Annual Symposium on Foundations of Computer Science, FOCS '97, Miami Beach, Florida, USA, October 19-22, 1997 , pp.\ 554--563. IEEE Computer Society, 1997. doi:10.1109/SFCS.1997.646145. URL https://doi.org/10.1109/SFCS.1997.646145

    work page arXiv 1997

  4. [4]

    and Sheffet, O

    Awasthi, P. and Sheffet, O. Improved spectral-norm bounds for clustering. In Gupta, A., Jansen, K., Rolim, J. D. P., and Servedio, R. A. (eds.), Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques - 15th International Workshop, APPROX 2012, and 16th International Workshop, RANDOM 2012, Cambridge, MA, USA, August 15-17, ...

    doi:10.1007/978-3-642-32512-0 2012

  5. [5]

    Stability yields a PTAS for k -median and k -means clustering

    Awasthi, P., Blum, A., and Sheffet, O. Stability yields a PTAS for k -median and k -means clustering. In 51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA , pp.\ 309--318. IEEE Computer Society, 2010. doi:10.1109/FOCS.2010.36. URL https://doi.org/10.1109/FOCS.2010.36

    doi:10.1109/focs.2010.36 2010

  6. [6]

    Efficiently computing similarities to private datasets

    Backurs, A., Lin, Z., Mahabadi, S., Silwal, S., and Tarnawski, J. Efficiently computing similarities to private datasets. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=HMe5CJv9dQ

    work page 2024

  7. [7]

    and Gottlieb, L

    Bartal, Y. and Gottlieb, L. Near-linear time approximation schemes for steiner tree and forest in low-dimensional spaces. In Khuller, S. and Williams, V. V. (eds.), STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21-25, 2021 , pp.\ 1028--1041. ACM , 2021. doi:10.1145/3406325.3451063. URL https://doi.org/10.114...

    arXiv 2021

  8. [8]

    W., and Drineas, P

    Boutsidis, C., Mahoney, M. W., and Drineas, P. Unsupervised feature selection for the k -means clustering problem. In Bengio, Y., Schuurmans, D., Lafferty, J. D., Williams, C. K. I., and Culotta, A. (eds.), Advances in Neural Information Processing Systems 22: 23rd Annual Conference on Neural Information Processing Systems 2009. Proceedings of a meeting h...

    work page 2009

Show all 50 references
  1. [9]

    Diversity maximization in doubling metrics

    Cevallos, A., Eisenbrand, F., and Morell, S. Diversity maximization in doubling metrics. In Hsu, W., Lee, D., and Liao, C. (eds.), 29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan , volume 123 of LIPIcs, pp.\ 3...

    2018 doi

  2. [10]

    An improved analysis of local search for max-sum diversification

    Cevallos, A., Eisenbrand, F., and Zenklusen, R. An improved analysis of local search for max-sum diversification. Math. Oper. Res., 44 0 (4): 0 1494--1509, 2019. doi:10.1287/MOOR.2018.0982. URL https://doi.org/10.1287/moor.2018.0982

    2019

  3. [11]

    Deterministic rounding for bipartite matching and GAP

    Chakrabarty, D. Deterministic rounding for bipartite matching and GAP . URL https://www.cs.dartmouth.edu/ deepc/LecNotes/Appx/6. Deterministic Rounding for Generalized Assignment Problem.pdf

  4. [12]

    and Halld \'o rsson, M

    Chandra, B. and Halld \'o rsson, M. M. Approximation algorithms for dispersion problems. Journal of algorithms, 38 0 (2): 0 438--465, 2001

    2001

  5. [13]

    and Waingarten, E

    Charikar, M. and Waingarten, E. The Johnson-Lindenstrauss Lemma for clustering and subspace approximation: From coresets to dimension reduction. CoRR, 2022

    2022

  6. [14]

    H.-C., and Krauthgamer, R

    Chen, X., Jiang, S. H.-C., and Krauthgamer, R. Streaming Euclidean max-cut: Dimension vs data reduction. In Proceedings of the 55th Annual ACM Symposium on Theory of Computing, pp.\ 170--182, 2023

    2023

  7. [15]

    Clarkson, K. L. Nearest neighbor queries in metric spaces. Discret. Comput. Geom., 22 0 (1): 0 63--93, 1999. doi:10.1007/PL00009449

    1999 doi

  8. [16]

    B., Elder, S., Musco, C., Musco, C., and Persu, M

    Cohen, M. B., Elder, S., Musco, C., Musco, C., and Persu, M. Dimensionality reduction for k-means clustering and low rank approximation. In Servedio, R. A. and Rubinfeld, R. (eds.), Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Por...

    2015

  9. [17]

    and Schwiegelshohn, C

    Cohen - Addad, V. and Schwiegelshohn, C. On the local structure of stable clustering instances. In Umans, C. (ed.), 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017 , pp.\ 49--60. IEEE Computer Society, 2017. doi:...

    2017 doi

  10. [18]

    and Gupta, A

    Dasgupta, S. and Gupta, A. An elementary proof of a theorem of Johnson and Lindenstrauss . Random Struct. Algorithms, 22 0 (1): 0 60--65, 2003. doi:10.1002/rsa.10073. URL https://doi.org/10.1002/rsa.10073

    2003 doi

  11. [19]

    Deep generative models for synthetic data: A survey

    Eigenschink, P., Reutterer, T., Vamosi, S., Vamosi, R., Sun, C., and Kalcher, K. Deep generative models for synthetic data: A survey. IEEE Access, 11: 0 47304--47320, 2023

    2023

  12. [20]

    The discrete p-dispersion problem

    Erkut, E. The discrete p-dispersion problem. European Journal of Operational Research, 46 0 (1): 0 48--60, 1990

    1990

  13. [21]

    Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering

    Feldman, D., Schmidt, M., and Sohler, C. Turning big data into tiny data: Constant-size coresets for k-means, pca, and projective clustering. SIAM J. Comput. , 49 0 (3): 0 601--657, 2020. doi:10.1137/18M1209854. URL https://doi.org/10.1137/18M1209854

    2020 doi

  14. [22]

    Composable coresets for determinant maximization: Greedy is almost optimal

    Gollapudi, S., Mahabadi, S., and Sivashankar, V. Composable coresets for determinant maximization: Greedy is almost optimal. Advances in Neural Information Processing Systems, 36, 2024

    2024

  15. [23]

    Diversity in machine learning

    Gong, Z., Zhong, P., and Hu, W. Diversity in machine learning. IEEE Access, 7: 0 64323--64350, July 2018

    2018

  16. [24]

    Gupta, A., Krauthgamer, R., and Lee, J. R. Bounded geometries, fractals, and low-distortion embeddings. In 44th Symposium on Foundations of Computer Science, FOCS , pp.\ 534--543. IEEE Computer Society, 2003. doi:10.1109/SFCS.2003.1238226

    2003 arXiv

  17. [25]

    H., Krauthgamer, R., and Yue, D

    Huang, L., Jiang, S. H., Krauthgamer, R., and Yue, D. Near-optimal dimension reduction for facility location. CoRR, 2024. doi:10.48550/ARXIV.2411.05432

    2024 doi arXiv

  18. [26]

    Sublinear time algorithms for metric space problems

    Indyk, P. Sublinear time algorithms for metric space problems. In Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing , pp.\ 428--434. ACM , 1999. doi:10.1145/301250.301366. URL https://doi.org/10.1145/301250.301366

    1999

  19. [27]

    and Motwani, R

    Indyk, P. and Motwani, R. Approximate nearest neighbors: Towards removing the curse of dimensionality. In Proceedings of the Thirtieth Annual ACM Symposium on the Theory of Computing, STOC , pp.\ 604--613, 1998. doi:10.1145/276698.276876. URL https://doi.org/10.1145/276698.276876

    1998

  20. [28]

    and Naor, A

    Indyk, P. and Naor, A. Nearest-neighbor-preserving embeddings. ACM Trans. Algorithms , 3 0 (3): 0 31, 2007. doi:10.1145/1273340.1273347. URL https://doi.org/10.1145/1273340.1273347

    2007

  21. [29]

    Indyk, P., Mahabadi, S., Mahdian, M., and Mirrokni, V. S. Composable core-sets for diversity and coverage maximization. In Proceedings of the 33rd ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, pp.\ 100--108, 2014

    2014

  22. [30]

    Dimensionality reduction for wasserstein barycenter

    Izzo, Z., Silwal, S., and Zhou, S. Dimensionality reduction for wasserstein barycenter. Advances in neural information processing systems, 34: 0 15582--15594, 2021

    2021

  23. [31]

    H., Krauthgamer, R., and Sapir, S

    Jiang, S. H., Krauthgamer, R., and Sapir, S. Moderate dimension reduction for k -center clustering. In 40th International Symposium on Computational Geometry (SoCG 2024), volume 293 of Leibniz International Proceedings in Informatics (LIPIcs), pp.\ 64:1--64:16. Schloss Dagstuh...

    2024

  24. [32]

    Johnson, W. B. and Lindenstrauss, J. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, 26: 0 189--206, 1984. URL https://api.semanticscholar.org/CorpusID:117819162

    1984

  25. [33]

    Kolliopoulos, S. G. and Rao, S. A nearly linear-time approximation scheme for the Euclidean k -median problem. SIAM J. Comput. , 37 0 (3): 0 757--782, 2007. doi:10.1137/S0097539702404055. URL https://doi.org/10.1137/S0097539702404055

    2007 doi

  26. [34]

    and Narayanan, S

    Mahabadi, S. and Narayanan, S. Improved diversity maximization algorithms for matching and pseudoforest. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Schloss Dagstuhl-Leibniz-Zentrum f \"u r Informatik, 2023

    2023

  27. [35]

    and Trajanovski, S

    Mahabadi, S. and Trajanovski, S. Core-sets for fair and diverse data summarization. Advances in Neural Information Processing Systems, 36, 2024

    2024

  28. [36]

    Makarychev, K., Makarychev, Y., and Razenshteyn, I. P. Performance of Johnson-Lindenstrauss transform for k -means and k -medians clustering. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC , pp.\ 1027--1038, 2019. doi:10.1145/3313276.3316350

    2019

  29. [37]

    A review on discrete diversity and dispersion maximization from an OR perspective

    Martí, R., Martínez-Gavara, A., Pérez-Peló, S., and Sánchez-Oro, J. A review on discrete diversity and dispersion maximization from an OR perspective. Eur. J. Oper. Res., 299 0 (3): 0 795--813, June 2022

    2022

  30. [38]

    and Mooney, R

    Melville, P. and Mooney, R. J. Diverse ensembles for active learning. In Twenty-first international conference on Machine learning - ICML '04, New York, New York, USA, 2004. ACM Press

    2004

  31. [39]

    F., Oh, S

    Naeem, M. F., Oh, S. J., Uh, Y., Choi, Y., and Yoo, J. Reliable fidelity and diversity metrics for generative models. ICML, 119: 0 7176--7185, February 2020

    2020

  32. [40]

    Randomized dimensionality reduction for facility location and single-linkage clustering

    Narayanan, S., Silwal, S., Indyk, P., and Zamir, O. Randomized dimensionality reduction for facility location and single-linkage clustering. In Proceedings of the 38th International Conference on Machine Learning, ICML , volume 139 of Proceedings of Machine Learning Research, ...

    2021

  33. [41]

    Is the k th central moment less than the k th raw moment for even k ? Mathematics Stack Exchange, 2021

    Nil, I. Is the k th central moment less than the k th raw moment for even k ? Mathematics Stack Exchange, 2021. URL https://math.stackexchange.com/q/4010466. author:https://math.stackexchange.com/users/242301/ixob-nil

    2021

  34. [42]

    J., and Swamy, C

    Ostrovsky, R., Rabani, Y., Schulman, L. J., and Swamy, C. The effectiveness of Lloyd -type methods for the k -means problem. J. ACM , 59 0 (6): 0 28:1--28:22, 2012. doi:10.1145/2395116.2395117. URL https://doi.org/10.1145/2395116.2395117

    2012

  35. [43]

    Intersecting diametral balls induced by a geometric graph

    Pirahmad, O., Polyanskii, A., and Vasilevskii, A. Intersecting diametral balls induced by a geometric graph. Discret. Comput. Geom., 71 0 (2): 0 480--497, 2024. doi:10.1007/S00454-022-00457-X. URL https://doi.org/10.1007/s00454-022-00457-x

    2024 doi

  36. [44]

    Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension

    Shenmaier, V. Efficient PTAS for the maximum traveling salesman problem in a metric space of fixed doubling dimension. Optim. Lett., 16 0 (7): 0 2115--2122, 2022. doi:10.1007/S11590-021-01769-2. URL https://doi.org/10.1007/s11590-021-01769-2

    2022 doi

  37. [45]

    B., Silva, V

    Tenenbaum, J. B., Silva, V. d., and Langford, J. C. A global geometric framework for nonlinear dimensionality reduction. science, 290 0 (5500): 0 2319--2323, 2000

    2000

  38. [46]

    and Hinton, G

    van der Maaten, L. and Hinton, G. Visualizing data using t-sne. Journal of Machine Learning Research, 9 0 (86): 0 2579--2605, 2008. URL http://jmlr.org/papers/v9/vandermaaten08a.html

    2008

  39. [47]

    E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt , S

    Virtanen, P., Gommers, R., Oliphant, T. E., Haberland, M., Reddy, T., Cournapeau, D., Burovski, E., Peterson, P., Weckesser, W., Bright, J., van der Walt , S. J., Brett, M., Wilson, J., Millman, K. J., Mayorov, N., Nelson, A. R. J., Jones, E., Kern, R., Larson, E., Carey, C. J...

    2020

  40. [48]

    Wainwright, M. J. Basic tail and concentration bounds, pp.\ 21–57. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019

    2019

  41. [49]

    Yang, Y., Ma, Z., Nie, F., Chang, X., and Hauptmann, A. G. Multi-class active learning by uncertainty sampling with diversity maximization. Int. J. Comput. Vis., 113 0 (2): 0 113--127, June 2015

    2015

  42. [50]

    Do not let privacy overbill utility: Gradient embedding perturbation for private learning

    Yu, D., Zhang, H., Chen, W., and Liu, T.-Y. Do not let privacy overbill utility: Gradient embedding perturbation for private learning. In International Conference on Learning Representations, 2021. URL https://openreview.net/forum?id=7aogOj_VYO0

    2021

Pith tools

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