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

We study a Weak-Strong Oracle (WSO) framework for discrete optimization problems in a metric space $(\mathcal{X},d)$. We assume the existence of a computationally expensive strong oracle ($\mathcal{S}\mathcal{O}$) that outputs exact distances between points, and a computationally cheap weak oracle (${\mathcal{W}\mathcal{O}}_{\alpha }$) that outputs $\alpha$-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 $(2{\alpha }^2+1)$-approximation using $O({\log }^{2}n)$ strong-oracle queries, and show that no algorithm using $o(n)$ strong queries can achieve an approximation factor below $2{\alpha }^2$. 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 $\Omega (n^2)$ strong-oracle queries, even for constant-factor approximation.