{"id":"0e1f75e5-6fab-42fa-8ee0-69b13c7e7611","arxiv_id":"2509.09652","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":8.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"A new correlation-rounding analysis yields the first polynomial-time additive approximation schemes for k-Euclidean Metric Violation and related low-rank problems.","lead":"We give the first polynomial-time additive approximation schemes for fitting low-dimensional Euclidean embeddings (k-EMV), improving on prior doubly exponential running times. The new rounding analysis for Sherali-Adams/SoS relaxations also yields new guarantees for weighted variants and entrywise low-rank approximation.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 5.10's entropy bound is incompatible with the grid Σ in Algorithm 5.5: with spacing ε/√k the support of truncated variables grows with √(E d^2), so B re-enters the conditioning-set size and the poly(n) runtime is not established.","rationale":"The reader's weakest_assumption focuses on Lemma 5.8, the anchoring step. That step is indeed important, and its proof has notational sloppiness, but the inequality itself can be repaired by standard triangle-type arguments. The more concrete blocker in the written proof is the entropy/grid mismatch: Lemma 5.10 is what removes B from the conditioning-set size, and its proof silently assumes a grid whose spacing scales with √(E d^2). Algorithm 5.5 does not define such a grid. With the stated grid, the support of the truncated variables contains Θ(2^B) points whenever the input distances have large scale, so the entropy potential is not O(k log(k/ε)) and the number of rounds in Lemma 5.11 grows with B. This directly undermines the claimed poly(n) runtime for Theorem 5.4 as written, since the SA degree and hence the LP size are affected. The issue is likely fixable by rescaling the grid, and the reader's conditional verdict remains appropriate, but it is a distinct and more load-bearing gap than the one highlighted by the reader.","tokens_in":55162,"tokens_out":25694,"duration_ms":300098,"concrete_test":"Take D with all nonzero entries = Δ=2^B (so E d^2 ≈ Δ^2) and k=1, ε fixed. Let μ place probability mass on an interval of length Θ(Δ) around the anchor on the grid Σ from Algorithm 5.5 (spacing ε). Compute H(\\tilde x_1) for a truncated variable: it is Θ(log(Δ/ε)) = Θ(B). Recompute Lemma 5.10's claimed O(log(1/ε)) bound; it fails. Then verify that replacing Σ by {0}∪{ε√(E d^2)(1+ε)^t} restores the bound and that the proofs of Lemmas 5.6 and 5.9 still go through with constants adjusted. If they do, the theorem is salvageable but requires the correction and should remain conditional; if not, the poly(n) runtime is unproven.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim of Theorem 5.4 can only hold if the conditioning set size is independent of B. Lemma 5.11 bounds |T| by O(k log(k/ε)/ε^4), invoking Lemma 5.10 for E_i H(\\tilde x_i) ≤ O(k log(Ck/ε)). But Lemma 5.10's proof derives this by dividing the support width 2C sqrt(eE∥xi−E xi∥^2) by a grid spacing of sqrt(ε/k)·E d^2. That is not the grid in Algorithm 5.5, whose Σ is {0}∪{ε√(1/k)(1+ε)^t} with minimum spacing ε/√k. On the stated grid, the number of reachable values in the truncation ball is about 2C√(Var_i)/(ε/√k); averaged this is at least k log(C√(6E d^2)√k/ε), which can be Ω(kB) because E d^2 may be Θ(2^{2B}). Then Lemma 5.11's |T| and the SA degree acquire a factor B, and the algorithm's n^{O(|T|)} running time is not poly(n) in the input size. The proof is internally inconsistent: either Lemma 5.10 assumes a distance-normalized grid (spacing ε√(E d^2/k)) or the entropy bound must be reworked. The anchor step (Lemma 5.8) is not the only fragile piece; even with a valid anchor, the finiteness of the entropy potential depends on this grid scaling.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes an additive approximation scheme for the k-Euclidean Metric Violation problem (k-EMV). Given pairwise distances D with B-bit entries, it claims to output an embedding in R^k whose k-EMV value is at most OPT_EMV + epsilon times the average squared input distance, in time (nB)^{poly(k,1/epsilon)} (stated as B^{poly} times poly(n) in Theorem 1.1). The approach combines a Sherali-Adams / Sum-of-Squares relaxation, a geometric discretization onto a grid, an anchoring step that conditions on a single point, and a global-correlation-rounding analysis showing that the objective terms are potential-aligned. The paper also claims extensions to weighted k-EMV under regularity assumptions and to entrywise ell_p low-rank approximation for even p > 2.","tokens_in":1741,"tokens_out":2067,"duration_ms":192676,"significance":"If correct, the main result would be the first polynomial-time additive approximation scheme for k-EMV and would settle the long-standing open question for k=1, since the additive error epsilon*E d^2 implies a (1+epsilon)-approximation when combined with the trivial bound OPT <= E d^2. The potential-aligned framework is a conceptually interesting extension of Barak-Raghavendra-Steurer correlation rounding to continuous low-dimensional embedding problems. The paper gives detailed proofs and does not rely on fitted parameters or circular reasoning. However, a load-bearing grid-scaling error in Lemma 5.10 currently invalidates the claimed poly(n) runtime for the central theorem. The manuscript needs a significant technical repair before its main contribution can be accepted.","major_comments":[{"comment":"The entropy bound in Lemma 5.10 uses the wrong grid spacing. The proof bounds H(tilde x_i) by dividing the support width 2C*sqrt(E||x_i - E x_i||^2) by a denominator sqrt(epsilon/k * E_{i,j} d_{ij}^2). But Algorithm 5.5 defines Sigma = {0} union {epsilon*sqrt(1/k)(1+epsilon)^t}, whose minimum spacing is epsilon/sqrt(k), independent of E d^2. On the stated grid, the number of reachable values in the truncation ball is Omega(C*sqrt(E d^2)*sqrt(k)/epsilon), and E d^2 can be Theta(2^{2B}) when min d_ij = 1 and max d_ij = 2^B. Thus the correct bound is O(kB), not O(k log(Ck/epsilon)). Consequently Lemma 5.11 gives |T| = Omega(kB/epsilon^4), the Sherali-Adams degree acquires B, and the algorithm's search/solution time has n^{Omega(B)} factors; the poly(n) runtime of Theorem 5.4 is not established. This is fixable by using a distance-normalized grid with spacing epsilon*sqrt(E d^2/k), but that","section":"§5.2, Lemma 5.10 vs. Algorithm 5.5"},{"comment":"The display 'OPTDEMV <= E(dij - ||xhat_i - xhat_j||)^2 = E(dij - ||xhat_i - xhat_j|| ± ||x_i - x_j||)^2 = OPT_EMV + epsilon E d^2 + ...' is not a valid identity. The first and third expressions are not equal, and the ± notation obscures the dependence on the optimal solution x. At best this should be an upper bound obtained by adding and subtracting ||x_i - x_j|| and applying triangle/Cauchy-Schwarz. The subsequent 16epsilon bound may be recoverable, but the proof as written contains a real algebraic gap in a load-bearing discretization lemma.","section":"§5.2, Lemma 5.6, Eq. (8)"},{"comment":"The weighted runtime stated in the body is inconsistent with the claimed Theorem 1.2. Theorem 5.12 claims time (n*Delta)^{O(k^2 log(Delta*k/(epsilon*delta))/(epsilon^2*delta^11))}; since Delta = 2^B can encode B bits, this is at least n^{Omega(k^2 B)} even for fixed epsilon and delta, so it is not of the form (n*2^B)^{poly(k,epsilon^{-1},delta^{-1})} promised in Theorem 1.2. The degree appearing in the final proof of Theorem 5.12 also contains log Delta. Unless the intended runtime is genuinely quasi-polynomial in n for growing B, the statement and proof need to be reconciled.","section":"§5.3, Theorem 5.12 vs. Theorem 1.2"}],"minor_comments":[{"comment":"The presentation of the low-diameter solution argument is hard to follow: 'all but an epsilon^2/Delta^4-fraction of pairs' and 'good points at least 1-epsilon/Delta^2' do not align dimensionally, and the sentence claiming 'there are only epsilon/Delta^2 n^2 many pairs' should be stated in terms of bad pairs/incidences. This is fixable but should be rewritten.","section":"§5.2, Lemma 5.6 / Fact 5.7"},{"comment":"The notation mu_T is overloaded: in Definition 3.4 it denotes the conditioned pseudo-distribution, while in Algorithm 5.5 step (b) it denotes the local distribution on T and then the conditioned distribution. This makes the algorithm ambiguous.","section":"§5.2, Algorithm 5.5 and Definition 3.4"},{"comment":"The expression 'x_i(T)' in the definition of tilde x_i appears to be a typo for x_i. Also, the statement 'all points in Sigma^k differ by at least sqrt(epsilon/k * E d^2)' should read 'differ by at least epsilon/sqrt(k)' for the actual Algorithm 5.5 grid; this is the same issue as the first major comment.","section":"§5.1, Lemma 5.10"},{"comment":"The speedup via [GS12a] is presented as a sketch. It should specify the number of rounds ell, the volume/measure condition needed for Theorem A.3, and precisely how the randomized SEED procedure satisfies the deterministic/framework hypotheses. As written, Appendix A is not self-contained enough to verify the claimed B^{poly}*poly(n) runtime.","section":"Appendix A"}],"recommendation":"major_revision","confidential_remarks":"I believe the central obstacle is the grid-spacing error in Lemma 5.10. It is likely repairable by normalizing the grid spacing by E d^2 and re-checking the discretization lemma, so I would not reject outright. If the authors cannot remove B from the entropy bound, then Theorem 5.4's polynomial-in-n claim fails and the manuscript's main contribution would need to be substantially weakened."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know. The paper is the first to claim a poly(n,B) additive approximation scheme for k-EMV via correlation rounding, and the overall architecture—anchoring, truncation, potential-aligned Lipschitz functions—is genuinely new. But as written the main theorem doesn't follow: Lemma 5.10's entropy bound is incompatible with the grid in Algorithm 5.5, and fixing it reintroduces B into the conditioning-set size, which breaks the claimed runtime.\n\nWhat's good: the framing of global correlation rounding for continuous low-dimensional embeddings is a real step; the weighted case and the even-p entrywise LRA results are also significant, and the related-work discussion is honest about what [DHKLU21] and [BCHJL25] do. The self-citations are contextual, not load-bearing. The proofs are spelled out in detail.\n\nThe soft spots. The stress-test note is correct, and I don't think it's a phantom objection. Lemma 5.10 claims all points in Σ^k differ by at least sqrt(ε/k·E d^2) per coordinate. That is false for the geometric grid used in Algorithm 5.5: near radius r the spacing is ε r, so within the truncation ball of radius C√Var_i the number of grid values per coordinate is about (1/ε) log(C√Var_i √k/ε). Averaging over i gives O(kB/ε) rather than O(k log(k/ε)) when E d^2 ~ 2^{2B}. Then Lemma 5.11's |T| picks up B, the SA degree becomes k^2 B/ε^4, and the runtime is no longer poly(n,B). This is a load-bearing issue, not a typo.\n\nThe other flagged items are minor by comparison: Eq. (8) in Lemma 5.6 has a phantom term and an equality that should be an inequality; Lemma 5.11 mentions a potential decrease with inconsistent units; Appendix A is explicitly a sketch and doesn't address the above. The Section A speedup relies on the same |T| bound, so it doesn't fix the gap.\n\nWho it's for: anyone working on hierarchy rounding, metric embedding, or ℓ_p LRA. It deserves a serious referee—the idea is plausible and the result, if repaired, is a substantial advance. I would want the entropy/discretization scaling reworked and the T-size argument redone before trusting the runtime.\n\nRecommendation: send to peer review. Don't desk reject. But the referee should be asked to check Section 5.1/5.2 carefully and demand a corrected Lemma 5.10 or a revised statement if the bound can't be made B-independent.","headline":"Genuinely new and likely salvageable, but Lemma 5.10's entropy bound is incompatible with the algorithm's own grid, and fixing it reintroduces B into the conditioning set—so the claimed polynomial runtime is not established as written.","tokens_in":56004,"tokens_out":9720,"would_cite":false,"duration_ms":111316,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68W25","68Q25","90C22"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper claims that k-Euclidean Metric Violation — fitting a k-dimensional Euclidean metric to arbitrary pairwise distances under squared error — admits the first polynomial-time additive approximation scheme, returning an embedding whose","keywords":["k-Euclidean Metric Violation","multidimensional scaling","additive approximation scheme","global correlation rounding","LP/SDP hierarchy","low-dimensional embedding","entrywise ℓ_p low-rank approximation"],"falsifier":"Search over small n and k=2 for a distance matrix D and an embedding with k-EMV objective at most 2 E_{ij} d_ij^2 but with every candidate anchor a satisfying (1/n)Σ_i‖x_i−x_a‖^2 > 6 E_{ij} d_ij^2; such an example would falsify Lemma 5.8 and collapse the anchoring step. Equivalently, on a small instance where the exact optimum is known by brute force, the algorithm should return objective at most OPT + ε E d^2 with high probability; a single violation would falsify the main theorem.","tokens_in":55053,"feed_emoji":"📐","tokens_out":9909,"duration_ms":111155,"temperature":0.7,"pith_summary":"The paper is trying to prove that the k-Euclidean Metric Violation (k-EMV) problem — fitting a k-dimensional Euclidean metric to an arbitrary matrix of pairwise distances under squared error — can be approximated in polynomial time with additive error ε times the average squared input distance, for every constant k. This problem, studied for decades as multidimensional scaling, was known to be NP-hard even when k=1, and no efficient approximation algorithms with guaranteed accuracy were known for k>1. The paper claims such a scheme exists, with the running time depending on the bit length B of the input distances as B raised to a power polynomial in k and 1/ε. It also extends the method to a weighted variant of k-EMV and to entrywise Lp low-rank approximation for even p>2. A sympathetic reader would care because these are the first worst-case guarantees of this kind for a widely used data-analysis task, and the technique adapts global correlation rounding from discrete optimization to continuous, unbounded domains.","feed_headline":"First polynomial-time additive scheme for k-EMV","feed_subtitle":"For any target dimension k, the algorithm's squared error beats the best fit by only an additive epsilon, in time polynomial in n and B.","key_machinery":"The load-bearing object is a pseudo-distribution from a convex-hierarchy relaxation, rounded by global correlation rounding: condition on values of a few coordinates sampled from the local distribution, then draw all remaining coordinates independently from their one-point marginals. The paper proves the objective's Lipschitz part (d_ij‖x_i−x_j‖) and quadratic part (⟨x_i,x_j⟩) are each 'potential-aligned' with an average-entropy potential and an average-variance potential; a combined-potential lemma bounds how many conditionings suffice to make the rounded expectation match the pseudo-expectation within ε. A truncation step replaces each variable by a bounded version, which is what keeps the","core_discovery":"Central claim is Theorem 5.4: for any input distance matrix D with B-bit entries, any target dimension k, and any 0<ε<1, an algorithm running in B^{O(k^2 log(k/ε)/ε^4)}·poly(n) time returns, with probability at least 0.99, an embedding in R^k whose k-EMV objective is at most OPT_EMV + ε·E_{ij} d_ij^2. The proof rounds a high-level convex-hierarchy relaxation (an LP/SDP pseudo-distribution) by first conditioning on a small anchor set and then sampling every remaining point independently from its one-point marginal. The new analysis shows the rounding error splits into a linear Lipschitz term and a quadratic covariance term, each controlled by a separate potential, so the number of conditionin","pith_inferences":["If the anchor lemma extends with dimension-independent constants and the B^{poly} factor can be made polylogarithmic, a full PTAS for k-EMV would follow directly from the same conditioning structure.","The truncation-before-rounding move is transferable to other continuous optimization problems where the objective splits into Lipschitz terms and polynomial terms but variables lie in an unbounded domain; the same potential-alignment argument would apply whenever a single conditioning step controls the variance.","One testable extrapolation: on synthetic low-dimensional embeddings corrupted by large global shifts or a few outliers, the algorithm's output should retain additive error ε·E d^2 because the first anchoring step kills global translations; measuring this empirically for small n and k=1 would probe the anchor lemma directly.","The ℓ_p result is confined to even integers because the proof expands (A_ij−u_i v_j)^p into monomials; getting odd p>2 will likely require non-monomial potentials beyond variance and entropy."],"forward_implications":["For fixed k and ε the running time is polynomial in n and B, replacing the earlier double-exponential dependence on the bit length B with a fixed polynomial degree.","The weighted version gives an additive approximation scheme for multidimensional scaling with partial or weighted pairwise data when the underlying weight graph is dense and regular, with an explicit dependence on density and distance magnitudes.","For entrywise ℓ_p low-rank approximation with even p>2, the technique yields a quasi-polynomial-time additive scheme with no bit-complexity assumptions, a guarantee not previously available even in subexponential time.","The paper states that the same rounding algorithms are likely to yield PTASs with different discretization schemes, though such a result would require new analytical ideas."],"fun_headline_variants":["First additive approximation scheme for k-EMV","Poly-time additive error for k-dimensional embeddings","Additive scheme for k-EMV: first poly-time result","Near-optimal embedding with additive error in poly time"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The load-bearing premise is Lemma 5.8: every embedding with objective value at most twice the average squared input distance has some anchor point such that the average squared distance from all points to that anchor is at most six times the average squared input distance; if this fails for k>1, the variance and entropy potentials that make the rounding finite are not bounded.","fun_headline_variants_meta":{"raw":{"variants":["First additive approximation scheme for k-EMV","Poly-time additive error for k-dimensional embeddings","Additive scheme for k-EMV: first poly-time result","Near-optimal embedding with additive error in poly time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000303,"raw_usage":{"total_tokens":1730,"prompt_tokens":1046,"completion_tokens":684,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":790,"completion_tokens_details":{"reasoning_tokens":621}},"tokens_in":790,"tokens_out":684,"duration_ms":7408,"temperature":1.0,"reasoning_tokens":621,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-04T18:45:52.683101+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Search over small n and k=2 for a distance matrix D and an embedding with k-EMV objective at most 2 E_{ij} d_ij^2 but with every candidate anchor a satisfying (1/n)Σ_i‖x_i−x_a‖^2 > 6 E_{ij} d_ij^2; such an example would falsify Lemma 5.8 and collapse the anchoring step. Equivalently, on a small instance where the exact optimum is known by brute force, the algorithm should return objective at most OPT + ε E d^2 with high probability; a single violation would falsify the main theorem.","supporting_citations":[],"review_version":1}