Not evaluated
Almost-linear-time exact matching in general graphs (family 120)
The gist
On October 6, 2026, OpenAI published a manuscript on computing a maximum matching (as many pairs as possible) in a general graph in almost-linear time.
DiscoverIA status on October 12, 2026: not evaluated, meaning no third-party evaluation found.
AI draft, not reviewedWhat has not been reviewed?
Text written by an AI (DiscoverIA pipeline), on . The status and its sources come from the registry; only the explanatory text has not been reviewed. A reported error is corrected, then the text is reviewed.
Cite this entry
A single status snapshot since Oct 12, 2026: a citation always points to a dated snapshot.
Cite snapshot 1, Oct 12, 2026
APA citation with the dated link
BibTeX @misc, key discoveria-oai-fam-120-almost-linear-time-exact-matching-general-r1
@misc{discoveria-oai-fam-120-almost-linear-time-exact-matching-general-r1,
author = {{DiscoverIA}},
title = {Almost-linear-time exact matching in general graphs (family 120)},
howpublished = {DiscoverIA registry, entry oai-fam-120-almost-linear-time-exact-matching-general},
note = {Status “Not evaluated”, snapshot 1, recorded on October 12, 2026. New result},
year = {2026},
url = {https://discoveria.ai/entry/oai-fam-120-almost-linear-time-exact-matching-general#releve-1},
urldate = {2026-10-12}
}Dated link opens this snapshot in the history
To understand ≈ 20 s reading time, estimated
What it changes
If the result held, the largest possible number of pairs could be formed in a general graph (a network of points joined by links, with no special structure) in almost-linear computing time, that is, a time growing only slightly faster than the size of the network. The subject belongs to theoretical computer science.
What remains unclear
No independent assessment is recorded, and OpenAI provides no Lean proof (a language in which a computer checks every step of a proof) for this family. The result comes from an internal model that OpenAI has not released.
For experts
Sources, method, key facts, status history, report an error
Status
Not evaluated
Recorded on · github.com · README.md
Step 1 of 4 on the scale: not evaluated. Next step: under review.
- Announced
- Recordednot evaluated
- nextTo follow
What this status means
Source reading : Source read word for word (level 3 of 3)
The result is declared neither right nor wrong.
To move to “Under review”: a public review under way. To “Peer reviewed”: a journal publication or a review by named experts.
Sources
- Main sourcegithub.com · CONTENTS.mdlink only, reading not recorded
- Repositorygithub.com · Almost-Linear-Time…link only, reading not recorded
Method
OpenAI publishes in its openai/math repository the manuscript “Almost-Linear-Time Maximum-Cardinality Matching in General Graphs”, dated September 24, 2026, the only manuscript of family 120, filed under the section “Theoretical computer science” of overview.tex. The repository folder is named “Almost-Linear-Time-Maximum-Cardinality-Matching-in-Sparse-General-Graphs-September-24-2026” whereas the manuscript title says “General Graphs”; history.md reports no revision. DiscoverIA status: not evaluated, meaning that no third-party evaluation has been found in the sources read. Set on October 12, 2026 from github.com (page read, quotation checked word for word: “Not all have accompanying Lean formalizations.”).
Limits
DiscoverIA has not checked this result itself.
Key facts
- Claimed by
- OpenAI (unreleased internal model)
announced on Oct 6, 2026 - Nature
- new result
- Field
- Theoretical computer science
- In openai/math
- family 120, section “Theoretical computer science”, 1 manuscript dated Sep 24, 2026
- Lean proof
- none supplied
- Revisions
- none reported by the claimant
- Checked by
- no verifier identified
- Sources
- 2 : 2 links only
- This entry
- AI draft, not reviewed
Status history
Only one observation so far.
- 01
First observation:Not evaluatedCurrent status
Family with no Lean proof supplied. No third-party evaluation read.
Source: github.comread word for word
An observation is added; none is ever erased.
In the same set
openai/math: 719 manuscripts in 372 families from an unreleased internal model · entry 117 of 372, by family number
- Not evaluated : Uniform sparsest cut: hardness and semidefinite gaps (family 117)
- Not evaluated : Unbounded bin-packing gaps and the modified integer round-up conjecture (family 118)
- Not evaluated : The Courtade–Kumar and Hellinger conjectures (family 119)
- Not evaluated : Almost-linear-time exact matching in general graphs (family 120)
- Not evaluated : Almost-linear expected-time approximation of edit distance (family 121)
- Not evaluated : Superpolynomial lower bounds and quasipolynomial reconstruction from deletion traces (family 122)
- Not evaluated : Polynomial-time scheduling on three identical machines (family 124)
Report an error or suggest a source
Thank you, your message was sent.
Sending failed. Try again, or write to contact@discoveria.ai.
Is your result listed?What each status requires, correcting this entry, replying to it.