acceptodds
Under review as a conference paper at ICLR 2027

On the Query Complexity of Metric Optimization under Weak–Strong Oracles

Abstract

We study a Weak-Strong Oracle (WSO) framework for discrete optimization problems in a metric space . We assume the existence of a computationally expensive strong oracle () that outputs exact distances between points, and a computationally cheap weak oracle () that outputs -approximate distances that can be corrupted by an adversary with some probability. The goal is to minimize the number of queries to the strong oracle while still accurately estimating global geometric structure. Our results reveal a structural asymmetry: while maximization problems such as diameter remain robust under adversarial corruption, minimization problems are significantly more sensitive. We give algorithms and complementary lower bounds for fundamental extremal distance problems in this model. For diameter estimation, we obtain a -approximation using strong-oracle queries, and show that no algorithm using strong queries can achieve an approximation factor below . More generally, we develop a lower-bound framework based on certifying edges and their overlap, which captures the difference between metric maximization and minimization problems. While maximization problems can admit sublinear-query algorithms, we show that metric minimization can require strong-oracle queries, even for constant-factor approximation.

Primary area:
learning theory
Keywords:
learning theory, optimization, graph theory

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_Ayz1OpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies a number of different metric optimization questions under the relatively new "weak-strong oracle" model. In this model we can query the distance between two points using a strong oracle, which returns the correct distance, or a weak oracle that with probability 2/32/3 returns an answer that is within α\alpha of the true distance, and with probability 1/31/3 is "corrupted" and returns an adversarially chosen value. The goal is to give a good approximation to the problem of interest while using very few strong oracle calls (obviously using (n2)\binom{n}{2} calls we could figure out all distances and then just solve our problem). Previous work has focused mostly on clustering problems, but this paper gives a variety of new results for many different problems.

They basically break these down into two "types": what they call "Max-Rigidity", where good approximations are possible with few strong oracle queries using an "anchor-median" algorithm (and which are generally maximization problems), and "Min-Fluidity", where essentially nothing nontrivial is possible (and which are generally minimization problems). One can intuitively think of diameter as a prototypical example of "max-rigidity", and closest pair as a prototypical example of min-fluidity. Intuitively, diameter is robust to mistakes: if (u,v)(u,v) have the maximum distance then for every other node ww at least one of the two is far from ww (by the triangle inequality), so if we sample a bunch of "anchor points" SS and then use the weak oracle on distances from everyone to SS, we'll get a good idea of what the maximum distance is. On the other hand, the closest pair is not robust: if you start with something like the uniform metric and hide one extremely short distance in a pair (u,v)(u,v), then there is no way to find this distance unless you actually use the strong oracle on (u,v)(u,v).

For the Max-Rigidity problems they give one meta-algorithm and show that it can be applied to each of the problems individually, and also give nearly-matching lower bounds. For the Min-Fluidity problems they design a general lower-bounding framework and apply it to each of the problems.

Overall, I do not think that this paper is up to the bar for ICLR. While the WSO model is interesting, the algorithms and the lower bounds in this paper are quite straightforward, and the algorithm in particular is just a straightforward adaptation of a previous algorithm used by Bateni et al. for clustering problems. The lower bounds are slightly more technically involved, but follow the obvious lower bound approach of starting with the uniform metric and then either hiding a bad pair (for min-fluidity) or a bad pair of nodes (for max-rigidity). Relatedly, the writing in this paper is a major issue -- perhaps because their techniques are relatively straightforward, they seem to claim a lot of things that are not formally backed up anywhere. At a high level, this paper reads to me as "a collection of pretty straightforward results in an interesting model, tied together through unnecessarily obscure writing".

Critical strengths
  • The WSO model has received some attention recently, and this paper gives some tight bounds for a variety of simple questions in this model.
Critical weaknesses
  • The writing of this paper was very strange. To me, it seems like the authors took an interesting new model (WSO), and proved some simple things for some very basic problems. This would be a reasonable contribution, although not quite as interesting as the previous work on WSO which mostly focuses on more interesting problems. But instead, they seem to insist on claiming some kind of generality which the results don't support. Most notably:

    • The first sentence in "Our Contributions" is

      In this paper, we perform a comprehensive study over the classes of metric optimization problems that admit guaranteed approximations with a “small number” of strong-oracle queries in the α\alpha-WSO model.

      This is a completely unjustified sentence. In no way is this study comprehensive -- it considers a small number of problems. There is no claim whatsoever that they characterize easy or hard problems, which would be necessary for a "comprehensive" study. More qualitatively, it only considers very "simple" problems, rather than problems that exhibit lots of interesting structure (like the clustering problems considered previously).

    • Possibly as a way of supporting their claim about comprehensiveness, they introduce the "max-rigidity" and "min-fluidity" concepts. But these don't actually mean anything! Neither of them is defined formally anywhere. So of course they cannot prove something like "every problem is one or the other", or even "a wide variety of problems fit inside this framework", since there are no actual definitions. But they seem to informally claim things like this, e.g., referring to their two notions as a "dichotomy" (see just before Corollary D.7) which by definition means that everything is on one side or the other. Again, it seems like they observed that some simple problems admit a similar algorithm (max-rigidity) or a similar lower bound (min-fluidity) and decided for some reason to phrase this as finding something fundamental about problems in the WSO model rather than just the (still reasonably interesting) fact that simple problems are somewhat simple.

  • The techniques do not seem super interesting to me, particularly on the upper bound side.

    • Their algorithm is essentially a simple variant of a previous algorithm of Bateni et al. So it's hard to see it as much of a contribution -- it was already defined, and doesn't do anything surprising.
    • The lower bounds are slightly more interesting, but even here they are relatively simple and dramatically oversold. Their lower bounds are basically of the form "start with the uniform metric, and define a bunch of nearby metrics that cause different answers and argue that many queries are needed to distinguish which metric we're in". This is the obvious approach, and the metrics that they consider are not particularly complicated or surprising. But they try to obscure this by going through various metatheorems and complicated definitions. This isn't valueless, but isn't particularly valuable either. To me, the "right" way to phrase these is to give one of them for a specific problem, and then say "the proofs of the other problems follow similar lines, see the appendix". But they don't do this, possibly because they want to claim more generality about max-rigidity and min-fluidity despite not actually defining either of them. It's hard for me to care too much about the meta-theorems when the class of problems has not actually been formally defined, or even defined informally in a convincing way.
Questions for authors
  • Is there an actual definition of max-rigidity and min-fluidity anywhere?
3 comments

The claim of a "comprehensive study" is unjustified; the paper studies a limited collection of relatively simple objectives.

Thank you for this feedback. We agree that "comprehensive" overstates the scope of our results. We do not characterize all easy and hard problems in the WSO model. We have replaced the opening claim in the updated version and revised the surrounding discussion to distinguish these results from the more general clustering problems studied in prior work.

Is there an actual definition of max-rigidity and min-fluidity? The claim of a dichotomy is unsupported.

There is no standalone formal definition of both labels as exhaustive classes of objectives. However, the underlying framework is formally defined. Definitions 4.2 and 4.3 specify perturbation families, certifying sets, certificate overlap, and flagged families, while Definition 5.1 specifies admissible single-edge contraction families. Theorem 4.4 states explicit conditions on these objects and acceptable output sets. In Section 2, we also describe the sparse-certificate mechanism quantitatively. We agree that referring to the informal labels as a "dichotomy" goes beyond these formal statements.

We have removed both labels and the dichotomy claim. Instead, we state the concrete geometric observation that a very short pair can be hidden in a uniform metric without changing any other distances, while making one pair sufficiently long requires neighboring distances to change as well. This observation motivates our examples, but is not a universal distinction between minimization and maximization. The formal general statement is Theorem 4.4, which gives sufficient conditions for a lower bound using a specified family of metrics, acceptable output sets, and certificate overlap.

The algorithm is a straightforward adaptation of Bateni et al., and the lower bounds use a familiar baseline-versus-perturbation approach.

We agree that the anchor-median method and the general indistinguishability approach are not new. The manuscript directly credits the algorithmic approach:

  • In Section 2, lines 137-139, we write, "For diameter, we adapt the anchor-and-median approach of Bateni et al. (2024)."
  • In Section 3, lines 174-177, we open by describing the algorithm as "an adaptation of the estimator of Bateni et al. (2024)."
  • In Section 1, lines 60-71, we credit their oracle model and summarize their clustering and MST results.

Our primary contribution is a common lower-bounding framework that establishes both approximation barriers for diameter and impossibility results for the minimization problems studied. For diameter, Theorem 4.8 shows that factors strictly below 2α22\alpha^2 require Ω(n)\Omega(n) strong queries, while factors below 22 require Ω(n2)\Omega(n^2) queries. Together with the (2α2+1)(2\alpha^2+1)-approximation using O(log⁡2n)O(\log^2 n) strong queries, this establishes the necessary quadratic dependence on α\alpha. The same framework yields a stronger obstruction for closest pair and several other metric minimization problems, concluding every fixed approximation factor requires Ω(n2)\Omega(n^2) strong queries. Thus, the framework captures both a threshold below which diameter approximation becomes expensive and problems for which no fixed approximation factor permits a sublinear number of queries in the number of candidate pairs.

The lower bounds would be clearer if a concrete problem were presented first and related applications were deferred to the appendix.

Thank you for this suggestion. We have improved the order of presentation by placing the concrete examples before the first informal meta-theorem, so that readers encounter the motivation before the terminology. These examples exist in Section 2, where we introduce the uniform-metric contraction example in lines 122-125 and the diameter dilation example in lines 152-158. We have further emphasized these motivating problems in the updated version. In Section 4.3, we also explicitly defer the formal application statements and proofs to Appendix D.3, and the contraction applications are summarized in Table 3, with detailed proofs in Appendix E.2.

The meta-theorem isolates the common information bottleneck for sublinear-query algorithms for the problems we study. The weak oracle leaves many perturbations plausible, while each strong query can distinguish only a limited number. It handles unlimited weak queries and adaptive strong queries once, reducing each application to checking a metric construction, its effect on acceptable outputs, and its certificate overlap. This yields lower bounds for each of the problems we study, and the list-recovery form handles structured outputs. Separate proofs would repeat this analysis, while the reusable theorem instead makes explicit which properties determine each bound.

The lower bounds are slightly more interesting, but even here they are relatively simple and dramatically oversold. Their lower bounds are basically of the form "start with the uniform metric, and define a bunch of nearby metrics that cause different answers and argue that many queries are needed to distinguish which metric we're in". This is the obvious approach, and the metrics that they consider are not particularly complicated or surprising. But they try to obscure this by going through various metatheorems and complicated definitions.

We believe the meta-theorem's technical contribution is to isolate and prove a reusable information bound for the weak-strong oracle model. The proof accounts for information from unlimited weak queries, establishes the conditional distribution of the hidden perturbation after observing those responses, and couples adaptive strong-query executions until a changed distance is queried. Certificate overlap then bounds how many candidates those queries can expose. The list-recovery statement additionally handles outputs that contain the hidden candidate without identifying it uniquely. These ingredients are proved once, and each application need only supply a metric family, an output-separation or list-recovery condition, and an overlap bound.

This abstraction has concrete uses beyond repeating the closest-pair argument. It yields strong-query lower bounds for diameter approximation, certified 1-center, and exact MST recovery. As detailed in our response concerning clustering, it also recovers the known Ω(k2)\Omega(k^2) strong-pair-query lower bounds of Bateni et al. for discrete metric kk-median and kk-means using a different metric family construction. Its applicability to extremal distances, sum objectives, and structured outputs demonstrates the benefit of a reusable theorem. We have also modified the presentation in the revised draft to remove claims such as a "comprehensive study" and a formal "dichotomy," and have emphasized the theorem’s sufficient conditions for lower bounds. Our novelty claim concerns this reusable theorem and the quantitative barriers it establishes.

I am going to leave my score where it is.

  • While I think the revision has improved the paper, the entire original storyline was about max-rigidity vs min-fluidity. Taking this out makes the paper an essentially different paper altogether, even with the same set of results. If the authors believe that it is not a significantly different paper, then I would find it slightly disturbing that the entire storyline can be replaced without changing the paper. That, to me, indicates a severe disconnect between the writing and the results. So I would encourage the authors to actually spend the time to write a clear and convincing paper and send it to the next appropriate conference.
  • Even with the changes to the intro, it still feels to me "like the authors took an interesting new model (WSO), and proved some simple things for some very basic problems" (as I said in my review). As the authors acknowledge, the upper bound is not particularly interesting. And I still don't think the lower bound is particularly exciting. The authors claim in their response that "Our novelty claim concerns this reusable theorem and the quantitative barriers it establishes." But while reusability is certainly a plus, it's not (in my opinion) a huge deal, particularly if the technique itself is relatively straightforward (as in this case).
Reviewer_FsoXOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies metric optimization with an expensive strong oracle that returns exact distances and a cheap weak oracle that returns α\alpha-approximate distances on uncorrupted pairs and potentially arbitrary values otherwise. It develops algorithms and lower bounds for diameter and related objectives, together with a certificate-overlap framework for strong-query lower bounds. Experiments illustrate the approach using edit-distance datasets and a simulated weak oracle.

Critical strengths

The setting is natural and potentially useful, and the paper is generally well written and easy to follow. The strongest contribution is the α\alpha-dependent diameter lower bound: achieving an approximation factor below 2α22\alpha^2 requires Ω(n)\Omega(n) strong queries, whereas the proposed algorithm achieves 2α2+12\alpha^2+1 with O(log⁡2n)O(\log^2 n) strong queries. This provides a near-matching approximation barrier for algorithms using a sublinear number of strong queries. The certificate-overlap framework also provides a common way to organize several lower-bound arguments.

Critical weaknesses

Much of the algorithmic development appears to extend the existing anchor-median method naturally. The paper needs a clearer account of which ingredients require new ideas and how the algorithms and lower bounds together advance understanding beyond prior work. The structural interpretation is also broader than the formal results. The certificate-overlap theorem supplies a sufficient condition for lower bounds; the broader interpretation about which objectives admit efficient algorithms should be clearly identified as intuition. Several applications remain closely related, making the scope of the proposed distinction particularly important to explain.

The edit-distance experiments mainly provide a controlled illustration of the analysis. Because the weak oracle is simulated, they offer limited evidence for practical computational savings. There are also concrete reporting inconsistencies. Figures 1 and 5 reuse the same plot under different dataset descriptions. At n=500n=500, Figure 1 gives a WSO estimate of approximately 18.4, while Table 7 reports 15.0. Table 8 describes a word dataset with α=1\alpha=1, whereas Section 6 and Figure 2 describe names with α=2\alpha=2. These discrepancies weaken the empirical support and require correction.

My current recommendation is 2 — Weak Reject. I could support 3 — Weak Accept if the authors correct the reporting discrepancies and convincingly explain the contribution beyond prior work, the scope of the structural claims, and the practical motivation.

Questions for authors

Does the proof of Theorem C.7 require minimizing over sampled centers? The upper-bound argument appears to use only the fact that every pairwise distance is at most 2R∗2R^*, where R∗R^* is the optimal radius. It therefore seems to give the same certified (2α2+2)(2\alpha^2+2)-approximation for a single fixed center, using only O(log⁡n)O(\log n) strong queries. Could the authors clarify this and revise the query bound if appropriate?

Which technical ingredients go beyond the existing anchor-median approach, and which parts of the broader structural interpretation should be understood as intuition? Alongside correcting the experimental discrepancies, could the authors describe a concrete inexpensive weak oracle whose guarantees plausibly fit the assumptions and explain the savings their results would enable?

3 comments

Which technical ingredients go beyond the existing anchor-median approach, and which structural claims should be understood as intuition?

Thank you for the careful assessment. We would first clarify that our paper credits this approach and does not claim that it is new.

  • In Section 2, lines 137-139, we write, "For diameter, we adapt the anchor-and-median approach of Bateni et al. (2024)."
  • In Section 3, lines 174-177, we open by describing the algorithm as "an adaptation of the estimator of Bateni et al. (2024)."
  • In Section 1, lines 60-71, we credit their oracle model and summarize their clustering and MST results. In particular, the diameter lower bound shows that an approximation factor strictly below 2α22\alpha^2 requires Ω(n)\Omega(n) strong queries, while our estimator, based on the existing anchor-median approach, achieves factor 2α2+12\alpha^2+1 with O(log⁡2n)O(\log^2 n) strong queries. This identifies the necessary quadratic dependence on α\alpha.

Our main technical contribution is the certificate-overlap meta-theorem (Theorem 4.4), which translates a family of metric perturbations into strong-query lower bounds for both objective estimation and solution recovery. It yields the diameter barriers of Ω(n)\Omega(n) queries for approximation factors below 2α22\alpha^2 and Ω(n2)\Omega(n^2) queries for factors below 22, as well as lower bounds for bipartite maxima, farthest-pair recovery, and certified discrete 1-center. Applied to single-edge contractions, it yields Ω(n2)\Omega(n^2) bounds for every fixed-factor approximation to closest pair and for exact MST recovery, together with Ω(n)\Omega(n) bounds for nearest neighbor. The technical intuition is that a legal weak oracle can leave many planted metrics plausible, while each exact query can distinguish only a limited number of them. The proof makes this precise by bounding the statistical difference between the baseline and planted weak transcripts, showing that the hidden candidate is conditionally uniform among the remaining possibilities, and coupling adaptive strong-query executions until a changed distance is queried. With KK candidate perturbations and certificate overlap ww, this gives an Ω(K/w)\Omega(K/w) bound. The resulting theorem provides formal sufficient conditions for hardness, and the broader contrast between contraction and dilation is intuition for these conditions.

Figures 1 and 5 reuse a plot under different dataset descriptions; Figure 1 disagrees with Table 7; Table 8 disagrees with Section 6 and Figure 2.

Thank you for identifying the issue. Figure 5 duplicated Figure 1 by mistake, and we have removed it from our paper. Table 7’s entry was a typo, which we have since fixed. We have regenerated this table from one run with 100 trials, each using one anchor set shared by all methods. Our results give a 0.950.95 confidence interval for the improvements made by our algorithm over both baselines. With a true diameter d=20d=20, at n=500n=500, α\alpha-WSO gives 18.6±0.618.6 \pm 0.6. The caption in Table 8 was a typo, and Table 8 reports the names data with α=2\alpha = 2. Regenerated with 100100 trials, the WSO results in a 0.950.95 confidence interval of 17.3−18.817.3-18.8, while the uniform sample gives 13.0−17.213.0-17.2. We note that below n=500n=500, nn does not yet exceed the Clog⁡nC\log n sampling threshold. When nn passes the threshold at n=1,000n=1,000, the 0.950.95 confidence interval from α−\alpha-WSO remains at 17.3−17.717.3-17.7 while the uniform sample drops to 13.0−14.313.0-14.3.

We also ran new experiments with a realistic weak oracle: the q-gram distance, which is the L1 distance between the count vectors of all length-q substrings of words using q=2q = 2. The strong oracle returns the exact edit distance. We ran the α\alpha-WSO algorithm with α=2\alpha=2 on the NLTK word corpus of ≤6\leq6 character words and a planted 2020-letter word that set the diameter. For every nn from 500500 to 16,00016,000, the estimate never exceeded dd and stayed above our guarantee d/(2α2+1)=d/9d/(2\alpha^2 + 1)=d/9. When the anchors contained at least a long word, it returned dd or d−1d-1. If the anchors missed all long words, the estimate came from the weak oracle and was still at least d/9d/9. We have added these results to the appendix.

Can the authors describe a concrete inexpensive weak oracle whose guarantees plausibly fit the assumptions and explain the savings?

The introduction supplies motivation for combining cheap and expensive similarity computations. Section 1 discusses the Google Now user-modeling example of Guha et al. and the comparisons used by KwikBucks. Another concrete candidate is a large sentence-embedding model paired with a smaller model trained to imitate its embeddings, commonly called a “teacher” and “student.” Sentence Transformers documents a four-layer student distilled from the 12-layer stsb-roberta-base model, achieving approximately 2.32.3 times higher encoding throughput. We can define the target metric using Euclidean distances between teacher embeddings and use student-embedding distances as cheap proxies. A smaller model trained on narrower data may approximate familiar inputs well but make large errors elsewhere, motivating our allowance for arbitrarily inaccurate weak responses.

Does Theorem C.7 require minimizing over sampled centers, or does one fixed center suffice with O(log⁡n)O(\log n) strong queries?

Thank you for pointing out this simplification. The proof does not use the minimization over sampled centers. Fix any c∈Xc\in X independently of the oracle responses, sample a set SS of m=Θ(log⁡n)m=\Theta(\log n) anchors, and query SO(c,t)\mathcal{SO}(c,t) for each t∈S∖{c}t\in S\setminus\{c\}. For each x distinct from c, define U(c,x) as the median of the values

SO(c,t)+αWOα(x,t)\mathrm{SO}(c,t) + \alpha \mathrm{WO}_{\alpha}(x,t)

over all anchors t in S distinct from both x and c. The same Chernoff and union-bound argument ensures that every such median has a strict majority of uncorrupted terms with probability 1−O(n−3)1-O(n^{-3}). Removing xx and cc removes at most two anchors and does not change the asymptotic sample size. For every uncorrupted term, the triangle inequality gives

\leq d(c,t)+\alpha^2d(x,t) \leq (2+2\alpha^2)R^*,$$ where the last inequality uses $d(y,z)\leq 2R^*$ for all $y,z\in X$. The median lies in the same interval, and $$R(c)\leq\widetilde R\leq(2\alpha^2+2)R^*.$$ Only $O(\log n)$ strong queries are needed, because the exact distances from $c$ to the anchors are reused for every target $x.$ We have revised Theorem C.7 accordingly. > Much of the algorithmic development appears to extend the existing anchor-median method naturally. The paper needs a clearer account of which ingredients require new ideas and how the algorithms and lower bounds together advance understanding beyond prior work. The paper's main contribution is a classification of when weak distances can replace exact distances for the objectives we studied. The upper bound alone would leave open whether its quadratic dependence on $\alpha$ reflects a limitation of the anchor-median estimator or the WSO framework itself. Our lower bound establishes that this dependence is necessary for every sublinear-strong-query algorithm. Factors strictly below $2\alpha^2$ require $\Omega(n)$ queries, while the adapted estimator achieves $2\alpha^2+1$ with $O(\log^2 n)$ queries. A second construction shows that factors below $2$ require $\Omega(n^2)$ queries. We contrast this result with the closest pair objective, where every fixed approximation factor requires $\Omega(n^2)$ strong queries despite unrestricted weak access. The common technical contribution is Theorem 4.4, which separates the geometry of a hard metric family from the information available through the two oracles. Its proof controls the statistical difference between weak-transcript distributions and accounts for adaptive strong-query executions. It gives a framework for producing lower bounds on numerical estimation and recovery of structured solutions. Together with the dilation construction, this establishes approximation factor bounds that are not supplied by adapting the existing anchor-median algorithm.

I appreciate the corrections to the figures and tables and the improvement to the 1-center result.

To clarify, my original review did not raise concerns about attribution and already recognized the value of the α\alpha-dependent lower bounds. However, I had taken those results into account and remained unconvinced that they alone represented a sufficiently substantial contribution. A substantial part of the paper develops anchor–median-based results, whose technical advance beyond natural extensions of Bateni et al. remains unclear.

Identifying the lower-bound framework as the main contribution does not fully address this concern. Specifically, the response does not clearly explain where Bateni et al.’s techniques are insufficient, what new ideas are needed to overcome those limitations, and why overcoming them constitutes a substantial technical advance. This unresolved concern about the overall contribution is the main reason I am maintaining my current score.

Reviewer_gVfYOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

In this paper, the author studies metric optimization with two types of distance oracles, building on the α\alpha-Weak-Strong Oracle model of Bateni et al. The strong-oracle queries return exact distances, but could be expensive. On the other hand, the weak-oracle queries are free but can be unreliable. Moreover, it allows a multiplicative distortion by a factor of α\alpha with probability 2/3 and adversarial corruption with probability 1/3.

The authors study how many strong-oracle queries are needed to approximate various metric optimization problems. For diameter and related maximization problems, they obtain a 2α2+12\alpha^2+1-approximation using O(log⁡2n)O (\log^2 n) strong-oracle queries. On the lower bounds side, they show that any diameter approximation factor strictly below 2α22\alpha^2 requires Ω(n)\Omega(n) strong-oracle queries. Conversely, for the minimization problems, achieving any fixed approximation factor also requires Ω(n2)\Omega(n^2) strong-oracle queries in the worst case.

Critical strengths
  1. The authors show an interesting separation between extremal optimization problems. Minimization problems, such as closest-pair identification, require much more exact distance information than maximization problems, even when unlimited weak-oracle queries are available.

  2. The lower-bound construction is clean and easy to understand. After observing the weak oracle, many planted worlds remain possible, and the argument bounds how many of these worlds adaptive strong-oracle queries can distinguish. The indistinguishability technique itself is standard, but its use in this oracle model is useful.

Critical weaknesses
  1. The upper bound algorithm largely follows the median distance-estimation technique of Bateni et al. The additional (α\alpha)-distortion is handled by a short argument using the triangle inequality. The lower bounds also follow the familiar approach of distinguishing a baseline metric from a perturbed one. Besides, several applications use essentially the same elementary contraction construction, while the diameter dilation family appears to be the main new ingredient. For these reasons, I find the overall contribution incremental. I would like the authors to explain more clearly which parts of their results require genuinely new ideas.

  2. I think the geometric intuition behind the lower-bound constructions could be explained much more directly. The paper considers a uniform metric in which every edge has length BB, and changes one edge to length aa. Every affected triangle then has side lengths (a,B,B)(a,B,B), so the metric condition requires 0≤a≤2B0\le a \le 2B. Hence, we can contract an edge arbitrarily close to zero without changing any other distance. This allows a very short pair to remain hidden without affecting the rest of the metric, whereas dilating an edge beyond 2B2B forces some neighboring distances to change, leaving additional traces that may reveal the planted instance. This seems to be the basic geometric intuition. The authors mention it, but I found it difficult to extract from the surrounding terminology.

  3. The order in which notation and definitions are introduced is difficult to follow. For instance, Theorem 4.4 uses (B0\mathcal{B} _0 and Bi\mathcal {B} _i without explaining in the main text that these are the acceptable output sets for the corresponding metrics. Algorithm 1 and Theorem 3.2 use Δmax⁡(A,B)\Delta _{\max}(A,B) in the main text, whereas the formal definition appears in Appendix B. Also, just before Theorem 2.1, a single paragraph introduces several crucial concepts, such as baseline and perturbed metrics, certifying sets, certificate overlap, and flagged families, with very little intuition about what they mean or why they are needed. I found this paragraph particularly difficult to follow because so many definitions are introduced at once.

  4. The term "Max Rigidity" is more misleading than helpful. It gives a simple observation based on the triangle inequality as though a separate structural property, even though no such property is formally defined. The terminology also suggests a connection to established rigidity theory, such as Laman's theorem for generic planar frameworks, where prescribed distances constrain possible geometric changes. The paper does not establish such a connection, so I would prefer the authors to avoid this terminology or provide a precise definition of what they mean by it.

  5. From what I understand, Theorem C.7 (the discrete certified 1-center guarantee) applies to any fixed center. If so, querying the distances from one fixed center to the sampled anchors should only require O(log⁡n)O(\log n) strong queries. Why is it necessary to evaluate all O(log⁡n)O(\log n) candidate centers? I could not figure out where the proof uses the minimization over these candidates. It would be helpful to clarify whether the stated O(log⁡2n)O(\log^2 n) query complexity can be reduced directly.

  6. This also makes me wonder whether similar simplifications are possible for the other objectives. The paper does not establish that O(log⁡2n)O(\log^2 n) queries are necessary for the approximation factors it achieves. The linear lower bounds apply to better approximation factors, so they do not settle this question. I would like to see a clearer discussion of which approximation and query-complexity tradeoffs remain open.

Questions for authors
  1. Can the diameter approximation factor be improved from 2α2+12\alpha^2+1 to 2α22\alpha^2 while retaining sublinear strong-query complexity? The lower bound rules out factors strictly below 2α22\alpha^2, but it does not resolve whether the additional 1 is necessary.
  2. Is O(log⁡2n)O(\log^2 n) strong-query complexity necessary to achieve the approx. factor 2α2+12\alpha^2+1, or could fewer queries suffice?Currently, there is no matching query lower bound presented at this approximation factor. The discussion of optimality should distinguish between the order of dependence on α\alpha, the tightness of the approximation factor, and the number of strong queries required.
  3. What does the proposed structural perspective tell us about kk-median and kk-means when \alpha>1? The introduction raises a broad question about the capabilities and limitations of the model, but the results focus on a relatively narrow collection of extremal objectives and certified 1-center. I would like the authors to explain what the framework tells us beyond these examples, or narrow the corresponding claims.
3 comments

The upper bound algorithm largely follows the median distance-estimation technique of Bateni et al. Which parts of the results require new ideas?

Thank you for this feedback. We would like to clarify that we explicitly attribute the algorithmic approach to Bateni et al.

  • In Section 2, lines 137-139, we write, "For diameter, we adapt the anchor-and-median approach of Bateni et al. (2024)."
  • In Section 3, lines 174-177, we open by describing the algorithm as "an adaptation of the estimator of Bateni et al. (2024)."
  • In Section 1, lines 60-71, we credit their oracle model and summarize their clustering and MST results. Thus, we do not present the anchor-median technique itself as new. Our contribution is the analysis of the approximation and query-complexity guarantees, together with lower bounds against arbitrary algorithms in the model. For diameter, we give a (2α2+1)(2\alpha^2+1)-approximation with O(log⁡2n)O(\log^2 n) strong queries and show that every approximation factor strictly below 2α22\alpha^2 requires Ω(n)\Omega(n) strong queries. Thus, the quadratic dependence on α\alpha is necessary for sublinear-query algorithms.

We believe our main contribution is a lower bounding framework which establishes both this lower bound on the diameter result and impossibility of sublinear approximation results for problems such as closest pair approximation. The lower bound construction combines metric dilation with the ambiguity permitted by multiplicative weak-oracle responses. Starting from a uniform metric of distance BB, we increase a planted pair to 2α2B2\alpha^2 B and its incident pairs to α2B\alpha^2 B. The neighboring changes preserve the triangle inequality but can share legal weak responses with the baseline, since their distortion is only α2\alpha^2. The proof must then account for the information in the entire weak transcript and for adaptive strong queries. The certificate-overlap theorem formalizes this by giving, with KK candidate perturbations and overlap ww, an Ω(K/w)\Omega(K/w) lower bound under its stated separation and success assumptions. We present the lower-bounding applications as consequences of this common construction. Corollary 5.3 specializes Theorem 4.4 to certificate overlap w=1w=1, and Section 5.2 and Table 3 collect its applications. We believe the value of the common theorem is that it handles both scalar estimation and solution recovery for a range of problems, rather than requiring a separate indistinguishability argument for each output type.

The geometric intuition behind the lower-bound constructions could be explained much more directly.

Thank you for the suggestion. We give geometric intuition in Section 2, lines 122-125, which describes contracting a single pair of a uniform metric and identifies the affected triangles to have lengths (a,B,B)(a,B,B). On lines 152-158, we explain that dilating the planted diameter requires neighboring changes that preserve the triangle inequality while remaining within overlapping weak-response intervals, imposing a constraint that does not affect the contraction construction. In Section 4.2, we repeat this intuition before the dilation construction. We agree that placing these examples together, before the introductory terminology, would make their contrast easier to follow.

We have amended our manuscript to provide the following intuition before the introductory terminology: In a uniform metric with distance BB, changing one pair to distance aa creates triangles with side lengths (B,B,a)(B,B,a), which are valid whenever 0<a≤2B0<a\leq 2B. Therefore, a pair can become arbitrarily short without changing any other distance. In contrast, increasing that pair beyond 2B2B requires changing neighboring distances. For contraction, only a query to the planted pair detects the change, whereas for dilation, neighboring queries may detect it as well. Our certificate-overlap parameter quantifies this difference for the particular families used in our lower bounds.

This intuition is also formalized in Proposition D.4, which demonstrates increasing the diameter beyond 22 times its baseline value forces at least n−2n-2 pairs to change. Lemma D.3 separately proves the 2α22\alpha^2 ceiling when all but one pair remain within the stated multiplicative window.

The order in which notation and definitions are introduced is difficult to follow.

Thank you for identifying this issue. We have modified our manuscript to define Δmax⁡(A,B):=max⁡a∈A,b∈Bd(a,b)\Delta_{\max}(A,B):=\max_{a\in A,b\in B}d(a,b) before Algorithm 1 and define BiB_i as the set of acceptable outputs on metric did_i before Theorem 4.4. The formal definitions of the baseline and perturbed metrics, the pairs on which they differ, the overlap of those sets, and the weak-oracle conditions that allow the perturbations to remain ambiguous are now introduced in the order they are used in our preliminaries and overview.

The term "Max Rigidity" is misleading without a formal definition or connection to rigidity theory.

We agree. We do not establish a connection to geometric rigidity theory, and these terms are not formally defined classes of objectives. We have removed the labels "Max-Rigidity" and "Min-Fluidity" and use direct descriptions of the algorithmic guarantees and lower-bound constructions. The formal results concern the specific objectives analyzed and the sufficient conditions of the certificate-overlap theorem.

Does Theorem C.7 apply to any fixed center, reducing the strong-query complexity to O(log⁡n)O(\log n)?

Thank you for pointing out this simplification. The proof does not use the minimization over sampled centers. Fix any c∈Xc \in X independently of the oracle responses, sample a set SS of m=Θ(log⁡n)m = \Theta(\log n) anchors, and query SO(c,t)\mathrm{SO}(c,t) for each anchor t≠ct \ne c. For each x distinct from c, define U(c,x) as the median of the values SO(c,t)+αWOα(x,t)\mathrm{SO}(c,t) + \alpha \mathrm{WO}_{\alpha}(x,t) over all anchors t in S distinct from both x and c.

R~=max⁡x≠cU(c,x).\widetilde{R} = \max_{x \ne c} U(c,x).

The same Chernoff and union-bound argument ensures that every such median has a strict majority of uncorrupted terms with probability 1−O(n−3)1-O(n^{-3}). Removing xx and cc removes at most two anchors and does not change the asymptotic sample size. For every uncorrupted term, the triangle inequality gives

d(c,x)≤d(c,t)+αWOα(x,t)≤d(c,t)+α2d(x,t)≤(2+2α2)R∗.d(c,x) \leq d(c,t) + \alpha \mathrm{WO}_{\alpha}(x,t) \leq d(c,t) + \alpha^2 d(x,t) \leq (2+2\alpha^2)R^*.

Here, the last inequality uses d(y,z)≤2R∗d(y,z) \leq 2R^* for all y,z∈Xy,z \in X. The median lies in the same interval, and

R(c)≤R~≤(2α2+2)R∗.R(c) \leq \widetilde{R} \leq (2\alpha^2+2)R^*.

Only O(log⁡n)O(\log n) strong queries are needed, because the exact distances from cc to the anchors are reused for every target x.x. We have revised Theorem C.7 accordingly.

Can the diameter approximation factor be improved to 2α22\alpha^2? Are O(log⁡2n)O(\log^2 n) strong queries necessary at the stated approximation factor? Could the other objectives admit similar simplifications?

Our results do not settle either question. The lower bound rules out factors strictly below 2α22\alpha^2 with o(n)o(n) strong queries, but it does not rule out 2α22\alpha^2 itself. We also do not prove that Ω(log⁡2n)\Omega(\log^2 n) queries are necessary for a (2α2+1)(2\alpha^2+1)-approximation. We have distinguished these three issues explicitly, clarifying the quadratic dependence on α\alpha is necessary, the necessity of the additive 1 remains unknown, and the optimal strong-query complexity at the achieved factor remains open.

What does the proposed structural perspective imply for kk-median and kk-means when k>1k>1?

Thank you for this question. Our framework can recover the Ω(k2)\Omega(k^2) strong-edge-query lower bound established by Bateni et al. for bounded-factor approximation to discrete metric kk-median and kk-means. This is an application of the framework, rather than a new clustering lower bound.

Partition the input into kk isolated points SS and a tight cluster OO of n−kn-k points. Set all distances within OO to 1 and all other distances to BB. For each candidate pair e∈(S2)e\in\binom S2, contract only its distance to 1. Each resulting instance remains a metric, giving an admissible contraction family with K=(k2)K=\binom{k}{2} and certificate overlap w=1w=1.

For the objective ∑xd(x,C)r\sum_x d(x,C)^r, where r=1r=1 for kk-median or 22 for kk-mean, the baseline optimum is Br+n−k−1B^r+n-k-1, whereas the planted optimum is n−kn-k. Choosing Br>c(n−k)B^r>c(n-k) forces every cc-approximate solution to place one center in OO, one at an endpoint of the planted pair, and one at every remaining isolated point. Hence the unique omitted point of SS identifies a list of k−1k-1 candidate pairs containing the planted pair. The list-recovery statement of Theorem 4.4 therefore gives q≥(1−η)p(k2)−(k−1)=Ω(k2).q\geq(1-\eta)p\binom{k}{2}-(k-1)=\Omega(k^2).

The construction illustrates the utility of the framework in recovering lower bounds for a variety of different objectives. The hidden contraction changes the allocation of centers, eliminating an expensive assignment and creating an arbitrarily large approximation gap. The meta-theorem then handles the information available from weak queries and adaptive strong queries. This recovers the known dependence on kk, including quadratic dependence on nn when k=Θ(n)k=\Theta(n).

Besides, several applications use essentially the same elementary contraction construction, while the diameter dilation family appears to be the main new ingredient. For these reasons, I find the overall contribution incremental. I would like the authors to explain more clearly which parts of their results require genuinely new ideas.

We believe the main technical contribution is the combination of the certificate-overlap theorem and metric constructions that establish quantitative approximation barriers. In particular, the diameter lower bound resolves whether the quadratic dependence on α\alpha in the adapted estimator is necessary, concluding every factor strictly below 2α22\alpha^2 requires Ω(n)\Omega(n) strong queries. The construction must simultaneously create this objective gap, preserve the triangle inequality, and prevent unlimited weak queries from revealing the neighboring distance changes through the blind window.

The meta-theorem supplies the information argument which turns this construction into a lower bound against arbitrary adaptive algorithms. It accounts for the information already available in the entire weak transcript, establishes uniformity of the hidden candidate among the flagged pairs, and bounds divergence from a baseline metric's transcript through certificate overlap. This yields both the Ω(K/w)\Omega(K/w) bound and the output-list bound wq+L=Ω(K)wq+L=\Omega(K). The latter can be used when the output contains the hidden pair without identifying it, as in exact MST recovery. The contraction applications are instantiations of this theorem and their proofs reuse the common information argument rather than constitute separate new techniques. The resulting bounds establish different limitations within the same oracle model for problems including diameter and closest-pair approximation.

Comments on the paper

1 comment

Hi

@authors: Thank you for adding your rebuttal.

@reviewers: please acknowledge the rebuttal and decide whether it affects your assessment and score.

AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.