Plectis Atlas
Search

↑ and ↓ move, Enter opens, Esc closes.

Show on the map

The metric k-median approximation threshold and recovery

OpenAI groups related papers into a “family”. OpenAI’s catalogue describes this one:

Gives a deterministic polynomial-time \((1+2/e+\varepsilon)\)-approximation for finite rational metric k-median with specified candidate facilities, for every fixed ε > 0. Assuming \(P\ne NP\), the optimal infimum approximation factor is \(1+2/e\). (OpenAI’s Lean note)

Lean is a language for mathematical statements and proofs that a computer can verify. The assessments below ask whether those statements express the result OpenAI describes here.

Both independent assessments find that the Lean statements express or imply the whole result described above. Read the assessments

What the papers state

Theorem 1.1

In The approximation threshold for metric k-median

The paper’s main theorem is shown as a possible match to OpenAI’s description. No review confirming the selection is recorded.

For every fixed \varepsilon>0, there is a deterministic algorithm which, given a finite rational metric k-median instance with 1\le k\le |F|, returns S\subseteq F, |S|\le k, such that

\sum_{j\in J}d(j,S)\le \left(1+\frac2e+\varepsilon\right)\OPT_k.

Its running time is polynomial in the binary encoding length of the instance. The polynomial may depend on \varepsilon.

The release does not say which paper theorem its catalogue describes. Both statements above are shown whole: the paper’s main theorem first, then the statement that shares the most wording with the description. The atlas has not reviewed either choice.

Two more possible matches

  • Theorem 1.2 (Global application) in Single-exponential recovery and bounded-price strictness for metric k-median.
  • Theorem 1.1 (Refined recovery) in Single-exponential recovery and bounded-price strictness for metric k-median.
Reported proof verification
Four Lean statements in the release; independent groups report that Comparator accepted runs for all these files at the version shown here.
Papers and explanations
Two current papers, each readable here as a page beside its PDF.

Papers

Each paper opens as a reading page in the browser, with the PDF beside it. The statements each paper opens with are on its reading page.

Single-exponential recovery and bounded-price strictness for metric k-median

Undated, current edition.

Read it herePDF

We give an exact-budget recovery algorithm for metric k-median with single-exponential dependence on the number of comparison clusters without accurate, distinct proxies in a supplied anchor solution. On positive integral metrics of polynomially bounded diameter, a sufficiently small total proxy error and logarithmically many such clusters yield a \((1+2/e+\varepsilon)\) approximation in polynomial time with arbitrarily high success probability. We also prove bounded-price strictness for one compatible execution of the logarithmic-surplus construction. Together the recovery and payment arguments give a randomized \((2-\sigma)\) approximation, for an absolute σ > 0, on arbitrary finite rational metrics, both with high probability and in expectation, while opening at most k facilities on every output.

The approximation threshold for metric k-median

Undated, current edition.

Read it herePDF

For every fixed ε > 0, we give a deterministic polynomial-time \((1+2/e+\varepsilon)\)-approximation for finite rational metric k-median with specified candidate facilities, opening at most k facilities. Under \(P\ne NP\), the infimum approximation factor in this model is therefore \(1+2/e\).

Four Lean statements in this family

Choose one to see it beside the paper theorem it is paired with.

For a configured theorem, the Comparator program tests whether OpenAI’s separate proof proves the exact Lean statement using only the allowed axioms. Some statement files instead configure definitions for comparison by name and type. Acceptance does not establish that a formal statement means the same thing as the paper’s theorem.

KMedianRecovery

The paper states

No paper theorem is paired with this Lean statement.

no paper statement matches the Lean text clearly enough to pair, so the closest candidates are listed below.

Statements it shares words with:

  • Theorem 1.2 (Global application) in Single-exponential recovery and bounded-price strictness for metric k-median.
  • Theorem 3.1 in The approximation threshold for metric k-median.
  • Theorem 1.1 in The approximation threshold for metric k-median.
  • Theorem 5.1 (Rounding a grid solution) in The approximation threshold for metric k-median.
  • Theorem 6.2 (Deterministic additive approximation) in The approximation threshold for metric k-median.
  • Theorem 4.7 (A successful sampling prefix) in Single-exponential recovery and bounded-price strictness for metric k-median.
  • Theorem 5.3 (Completion of a prefix) in Single-exponential recovery and bounded-price strictness for metric k-median.
  • Theorem 1.1 (Refined recovery) in Single-exponential recovery and bounded-price strictness for metric k-median.

The Lean statement

No paper theorem is paired with it.

Randomized metric $k$-median approximation below two

KMedianRecovery.lean, the release lists it as a main result.

def globalApplicationClaim : Prop :=  ∃ σ : ℝ, 0 < σ ∧ ∀ a : ℝ, 0 < a → ∃ A : BinaryRandomizedAlgorithm,    (∀ (I : RationalMetricInput) (s : A.Seed I), I.Feasible (A.output I s)) ∧    (∀ I : RationalMetricInput,      1 - Real.rpow ((I.size : ℝ) + 2) (-a) ≤        A.successProbability I ((2 - σ) * (I.optimum : ℝ))) ∧    (∀ I : RationalMetricInput, A.expectedCost I ≤ (2 - σ) * (I.optimum : ℝ))theorem global_application : globalApplicationClaim := by  sorry

This file states the theorem with sorry, a placeholder, in place of its proof. OpenAI supplies a separate proof file. Comparator tests whether that proof proves the statement here.

two independent groups report that Comparator accepted runs for this Lean statement file: cert-machine; MathVet. Who ran the proof-verification program

  • cert-machine records it as “CERTIFIED”.
  • MathVet records it as “comparator-sandboxed-pass”.

Read the complete Lean statement

KMedianRefinedRecovery

The paper states

Theorem 1.1 (Refined recovery)

In Single-exponential recovery and bounded-price strictness for metric k-median

Let D and F be disjoint indexed sets in a metric whose distances between distinct indices are positive integers bounded by a fixed polynomial in N=|D|+|F|. Fix \varepsilon>0 and 0<L_0<\infty, and choose a fixed rational parameter

0<\mu\le \min\{1/4,\varepsilon/12\}.

Let S\subseteq F have cardinality h\ge1. Suppose there exists a comparison solution O\subseteq F of cardinality h and cost P>0, with a partition into good and bad centers and distinct proxies \phi_i\in S for the good centers, such that

\sum_{i\ \mathrm{good}}\sum_{p\in C_i}d(p,\phi_i) \le P_g+\mu P, \qquad m:=|\{i:i\ \mathrm{bad}\}|\le L_0\log N.

Given S, \mu, L_0, and a failure parameter \zeta\in(0,1), a randomized algorithm returns \widehat S\subseteq F with

|\widehat S|\le h \quad\text{always},\qquad \operatorname{cost}(\widehat S) \le (1+2/e+\varepsilon)P \quad\text{with probability at least }1-\zeta.

Its running time is polynomial in N and \log(1/\zeta) for the fixed parameters. The algorithm is not given O, P, the partition, or its proxies.

The words they share: 1/4, choose, disjoint, refined, centers, distances, min, recovery, bad, positive, zeta, good, log, integers, proxies, randomized, bounded, probability, rational, metric, cost, algorithm, time, polynomial, varepsilon, distinct, always, comparison, suppose.

Possible Lean counterpart

Selected from shared wording. No review of whether the statements mean the same thing is recorded.

Exact-budget recovery from accurate distinct cluster proxies

KMedianRefinedRecovery.lean, the release lists it as a supporting statement.

theorem refined_recovery :    ∀ (bound : Polynomial ℕ) (ε L₀ : ℝ) (μ : ℚ),      0 < ε → 0 < L₀ → 0 < μ → μ ≤ 1/4 → (μ : ℝ) ≤ ε/12 →      ∃ A : BinaryRandomizedAlgorithm,        PolynomialWork A bound ∧        ∀ I : Input, I.Bounded bound → ∀ ζ : ℝ, 0 < ζ → ζ < 1 →          (∀ s : Seed A I ζ, I.metric.Feasible (output A I ζ s)) ∧          (∀ C : Certificate I μ L₀,            1 - ζ ≤ successProbability A I ζ              ((1 + 2 / Real.exp 1 + ε) * (I.metric.cost C.centers : ℝ))) := by  sorry

This file states the theorem with sorry, a placeholder, in place of its proof. OpenAI supplies a separate proof file. Comparator tests whether that proof proves the statement here.

two independent groups report that Comparator accepted runs for this Lean statement file: cert-machine; MathVet. Who ran the proof-verification program

  • cert-machine records it as “CERTIFIED”.
  • MathVet records it as “comparator-sandboxed-pass”.

Read the complete Lean statement

KMedianThreshold

The paper states

The words they share: infimum, np, factors, specified, deterministic, approximation, facilities, time, polynomial.

Possible Lean counterpart

Selected from shared wording. No review of whether the statements mean the same thing is recorded.

Exact approximation threshold under $P\ne NP$

KMedianThreshold.lean, the release lists it as a supporting statement.

theorem threshold (h : Complexity.PNeNP) :    sInf approximationFactors=1+2/Real.exp 1 := by  sorry

This file states the theorem with sorry, a placeholder, in place of its proof. OpenAI supplies a separate proof file. Comparator tests whether that proof proves the statement here.

two independent groups report that Comparator accepted runs for this Lean statement file: cert-machine; MathVet. Who ran the proof-verification program

  • cert-machine records it as “CERTIFIED”.
  • MathVet records it as “comparator-sandboxed-pass”.

Read the complete Lean statement

MetricKMedian

The paper states

Theorem 1.1

In The approximation threshold for metric k-median

For every fixed \varepsilon>0, there is a deterministic algorithm which, given a finite rational metric k-median instance with 1\le k\le |F|, returns S\subseteq F, |S|\le k, such that

\sum_{j\in J}d(j,S)\le \left(1+\frac2e+\varepsilon\right)\OPT_k.

Its running time is polynomial in the binary encoding length of the instance. The polynomial may depend on \varepsilon.

The words they share: encoding, length, finite, rational, algorithm, time, varepsilon, deterministic, median, metric, polynomial.

Possible Lean counterpart

Selected from shared wording. No review of whether the statements mean the same thing is recorded.

Deterministic metric $k$-median approximation at the threshold

MetricKMedian.lean, the release lists it as a supporting statement.

theorem main_finite_work : ∀ ε : ℝ, 0 < ε →    ∃ (algorithm : Instance → List Bool) (P : Turing.TM2ComputableInPolyTime encodeInstance id algorithm),      (∀ k : P.tm.K, Finite (P.tm.Γ k)) ∧ ∀ I, Correct ε I (algorithm I) := by  sorry

This file states the theorem with sorry, a placeholder, in place of its proof. OpenAI supplies a separate proof file. Comparator tests whether that proof proves the statement here.

two independent groups report that Comparator accepted runs for this Lean statement file: cert-machine; MathVet. Who ran the proof-verification program

  • cert-machine records it as “CERTIFIED”.
  • MathVet records it as “comparator-sandboxed-pass”.

Read the complete Lean statement

Other mathematical statements in OpenAI’s Lean library

Atlas found these propositions by scanning the text of the project’s Model.lean file. Each name links to its definition, with any associated statement file beside it. This list does not record running Lean to interpret or verify those definitions.

Independent comparisons and proof-verification reports

Does the Lean express the advertised result?

MathVet and cert-machine agree on how much of the advertised result the Lean statements express.

MathVet and Carlos Toledo’s cert-machine independently assessed whether this family’s Lean statements express the whole result OpenAI describes in its catalogue. These are assessments of the family as a whole, not of each paper theorem separately.

MathVet finds that the Lean statements express or imply the whole advertised result (their term: “full”).

Their note: None; the hardness half is proven inside the threshold theorem under PNeNP (as the summary says ‘assuming P != NP’).

Definitions the group asks readers to compare with the paper: Complexity classes are hand-defined from Mathlib TM2ComputableInPolyTime with a FinitePolyTime finite-alphabet clause: P, NP (certificate form with encodePair) and PNeNP := P ≠ NP; approximationFactors is a set of reals whose sInf must be nonempty/bounded below (true: ≥ 1)

“full”, in their words: The challenge statements imply the headline claim after unpacking definitions or one routine step.

Their method: An independent, model-assisted, pre-referee reading of each family’s challenge statements against its headline claim under a published rubric (PROTOCOL.md), with its own Comparator runs per challenge.

Read the original assessment Read MathVet’s method

cert-machine finds that the Lean statements express or imply the whole advertised result (their term: “MATCHES”).

“MATCHES”, in their words: The challenge statements state the headline as OpenAI wrote it.

Their method: Every Comparator challenge re-run on Linux with nanoda switched on, decided by a preregistered rule.

Read the original assessment Read cert-machine’s method

OpenAI’s own note on what its Lean covers

The formalization gives an exact-budget recovery algorithm for metric $k$-median on the stated polynomially bounded integral metrics. Suppose a supplied anchor represents all but logarithmically many comparison clusters by distinct proxies, with total proxy cost at most the comparison cost plus a sufficiently small relative error. The algorithm always opens at most $k$ facilities and, with any requested confidence, attains a $(1+2/e+\varepsilon)$ factor relative to those comparison centers in polynomial time.

The linked final approximation result applies to arbitrary finite rational metrics. For one absolute $\sigma>0$, a polynomial-time fair-bit algorithm always returns a feasible solution, has expected cost at most $(2-\sigma)\mathrm{OPT}$, and attains the same factor with arbitrarily high polynomial confidence. The formalization gives, for every fixed $\varepsilon>0$, a deterministic polynomial-time $(1+2/e+\varepsilon)$-approximation for metric $k$-median on finite rational metrics with specified candidate facilities. Every output is a nonempty subset of the candidate facilities and opens at most $k$ of them. Assuming $P\ne NP$, it also proves that the infimum of all polynomial-time approximation factors in this model is exactly $1+2/e$.

AI-drafted comparisons, with no recorded human review

  • Randomized metric $k$-median approximation below two KMedianRecovery

    Unreviewed AI draft: states a paper’s theorem as the paper does. States the paper’s global application theorem: for one absolute σ > 0, a randomised polynomial-time k-median algorithm with expected cost at most (2 − σ)OPT on finite rational metrics.

  • Exact-budget recovery from accurate distinct cluster proxies KMedianRefinedRecovery

    Unreviewed AI draft: states a paper’s theorem as the paper does. States the paper’s refined recovery theorem: from an anchor with accurate distinct cluster proxies, an exact-budget algorithm attaining factor 1 + 2/e + ε on polynomially bounded integral metrics.

  • Exact approximation threshold under $P\ne NP$ KMedianThreshold

    Unreviewed AI draft: states a consequence of a paper’s theorem. States the paper’s threshold corollary: assuming P ≠ NP, the infimum of polynomial-time approximation factors is exactly 1 + 2/e. It combines the main algorithm with a hardness bound; attainment is not asserted.

  • Deterministic metric $k$-median approximation at the threshold MetricKMedian

    Unreviewed AI draft: states a paper’s theorem as the paper does. States the main theorem of the threshold paper: a deterministic polynomial-time (1 + 2/e + ε)-approximation for metric k-median with candidate facilities.

Who ran the proof-verification program?

These groups report running Comparator with the release’s Lean statement files. For a configured theorem, it verifies OpenAI’s separate proof against the exact statement; some files instead configure definitions for comparison by name and type. Each row is the named group’s report. Atlas has not repeated the runs.

These reports do not list the software versions, proof-verification programs, axioms, time or memory in separate fields. Any such details in a report’s prose are reproduced below.

Randomized metric $k$-median approximation below two KMedianRecovery

Two reports, all at the release’s recorded version.

Reported byTheir wordTheir accountDateOriginal report
cert-machine“CERTIFIED”Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution.10 October 2026Original report
MathVet“comparator-sandboxed-pass”Re-run through Comparator in a sandboxed virtual machine: accepted.8 October 2026Original report

Exact-budget recovery from accurate distinct cluster proxies KMedianRefinedRecovery

Two reports, all at the release’s recorded version.

Reported byTheir wordTheir accountDateOriginal report
cert-machine“CERTIFIED”Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution.10 October 2026Original report
MathVet“comparator-sandboxed-pass”Re-run through Comparator in a sandboxed virtual machine: accepted.8 October 2026Original report

Exact approximation threshold under $P\ne NP$ KMedianThreshold

Two reports, all at the release’s recorded version.

Reported byTheir wordTheir accountDateOriginal report
cert-machine“CERTIFIED”Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution.10 October 2026Original report
MathVet“comparator-sandboxed-pass”Re-run through Comparator in a sandboxed virtual machine: accepted.8 October 2026Original report

Deterministic metric $k$-median approximation at the threshold MetricKMedian

Two reports, all at the release’s recorded version.

Reported byTheir wordTheir accountDateOriginal report
cert-machine“CERTIFIED”Re-run through Comparator with the independent nanoda kernel switched on: Lean’s kernel and nanoda both accept OpenAI’s solution.10 October 2026Original report
MathVet“comparator-sandboxed-pass”Re-run through Comparator in a sandboxed virtual machine: accepted.8 October 2026Original report

What these papers cite in the release, and what cites them

These links come from the papers’ bibliographies. A citation records that one paper cites another; how each cited result is used has not been examined here.

Within this family

Papers elsewhere in the release that this family’s papers cite

This family’s papers cite no paper elsewhere in the release.

Papers elsewhere in the release that cite this family’s papers

No paper elsewhere in the release cites this family’s papers.

References outside the release

Each paper’s outside references are listed with it on its reading page, where each citation is placed. Every outside work cited in the release: References outside the release

Explain a result, compare statements or propose a correction

Atlas has no contributed explanation for this family yet. You can offer one with a GitHub account. You receive named credit and disclose any AI assistance.

Each button opens a GitHub form with this page and its source version filled in. Opening the form does not reserve the work.

Offer to write an explanationCompare one Lean statement with its paper: KMedianRecovery, KMedianRefinedRecovery, KMedianThreshold, MetricKMedianSuggest a source attributionSuggest a change

What people have said

Commentary on this family by others, dated and credited. It is commentary, not a finding.

  • An unsigned public tier list, the OpenAI Math Tier List, classes it as a algorithm and rates its significance, if it holds up, as “Major math journal”. The page says that nothing on it is verified.

    Author not stated. Source

Questions awaiting review

Each item identifies a statement, definition or report that needs further review. Its link opens a GitHub form with the source version already recorded.

Read the Lean statement against the paper

  • An AI agent drafted an assessment of which part of the paper this Lean statement expresses. No named human review is recorded. Open the form
  • An AI agent drafted an assessment of which part of the paper this Lean statement expresses. No named human review is recorded. Open the form
  • An AI agent drafted an assessment of which part of the paper this Lean statement expresses. No named human review is recorded. Open the form
  • An AI agent drafted an assessment of which part of the paper this Lean statement expresses. No named human review is recorded. Open the form

Identify the theorem the catalogue describes

  • Family 125 The theorem shown was selected from shared wording with OpenAI’s description. Atlas records no review confirming that it is the theorem the description means. Open the form

Address a question raised in an independent assessment

Compare the proposed paper and Lean matches

  • Family 125 Atlas records no review of whether each linked Lean statement and paper theorem mean the same thing. Open the form